التراجع الكارثي

Some regular expressions are looking simple, but can execute a veeeeeery long time, and even “hang” the JavaScript engine.

Sooner or later most developers occasionally face such behavior. The typical symptom – a regular expression works fine sometimes, but for certain strings it “hangs”, consuming 100% of CPU.

في مثل هذه الحالة ، يقترح متصفح الويب إنهاء البرنامج النصي وإعادة تحميل الصفحة. ليس بالشيء الجيد بالتأكيد

For server-side JavaScript such a regexp may hang the server process, that’s even worse. So we definitely should take a look at it.

مثال

Let’s say we have a string, and we’d like to check if it consists of words \w+ with an optional space \s? after each.

An obvious way to construct a regexp would be to take a word followed by an optional space \w+\s? and then repeat it with *.

That leads us to the regexp ^(\w+\s?)*$, it specifies zero or more such words, that start at the beginning ^ and finish at the end $ of the line.

في العمل:

let regexp = /^(\w+\s?)*$/;

alert( regexp.test("A good string") ); // true
alert( regexp.test("Bad characters: $@#") ); // false

The regexp seems to work. The result is correct. Although, on certain strings it takes a lot of time. So long that JavaScript engine “hangs” with 100% CPU consumption.

If you run the example below, you probably won’t see anything, as JavaScript will just “hang”. A web-browser will stop reacting on events, the UI will stop working (most browsers allow only scrolling). After some time it will suggest to reload the page. So be careful with this:

let regexp = /^(\w+\s?)*$/;
let str = "An input string that takes a long time or even makes this regexp hang!";

// will take a very long time
alert( regexp.test(str) );

To be fair, let’s note that some regular expression engines can handle such a search effectively, for example V8 engine version starting from 8.8 can do that (so Google Chrome 88 doesn’t hang here), while Firefox browser does hang.

مثال مبسط

What’s the matter? Why does the regular expression hang?

لفهم ذلك ، دعنا نبسط المثال: إزالة المسافات \ s؟. ثم يصبح النمط: ^ (\ w +) * $.

ولجعل الأمور أكثر وضوحًا ، دعنا نستبدل \ w بـ \ d. مازال التعبير العادي الناتج معلقًا ، على سبيل المثال:

let regexp = /^(\d+)*$/;

let str = "012345678901234567890123456789z";

// will take a very long time (careful!)
alert( regexp.test(str) );

إذن ما هو الخطأ في regexp؟

أولاً ، قد يلاحظ المرء أن نمط regexp : (\ d +) * غريب بعض الشيء. يبدو "نمط محدد الكمية: *غريبًا. إذا أردنا رقمًا ، فيمكننا استخدامpattern: \ d +`.

Indeed, the regexp is artificial; we got it by simplifying the previous example. But the reason why it is slow is the same. So let’s understand it, and then the previous example will become obvious.

What happens during the search of ^(\d+)*$ in the line 123456789z (shortened a bit for clarity, please note a non-digit character z at the end, it’s important), why does it take so long?

Here’s what the regexp engine does:

1. First, the regexp engine tries to find the content of the parentheses: the number \d+. The plus + is greedy by default, so it consumes all digits:

\ d + .......     (123456789) z

After all digits are consumed, `pattern:\d+` is considered found (as `match:123456789`).

Then the star quantifier `pattern:(\d+)*` applies. But there are no more digits in the text, so the star doesn't give anything.

The next character in the pattern is the string end `pattern:$`. But in the text we have `subject:z` instead, so there's no match:

```
           X
\d+........$
(123456789)z
```

2. نظرًا لعدم وجود تطابق ، فإن نمط المحدد الكمي الجشع : + يقلل من عدد التكرار ، ويعيد حرفًا واحدًا إلى الوراء.

   Now \d+ takes all digits except the last one (12345678):

   \d+.......
   (12345678)9z

3. Then the engine tries to continue the search from the next position (right after 12345678).

   The star (\d+)* can be applied – it gives one more match of \d+, the number 9:

``

\d+.......\d+
(12345678)(9)z
```

The engine tries to match `pattern:$` again, but fails, because it meets `subject:z` instead:

X     \ d + ....... \ d +     (12345678) (9) z

4. There’s no match, so the engine will continue backtracking, decreasing the number of repetitions. Backtracking generally works like this: the last greedy quantifier decreases the number of repetitions until it reaches the minimum. Then the previous greedy quantifier decreases, and so on.

تتم محاولة جميع التركيبات الممكنة. هنا أمثلةهم.

يتكون الرقم الأول من النمط: \ d + من 7 أرقام ، ثم عدد من رقمين:

```
             X
\d+......\d+
(1234567)(89)z
```

يتكون الرقم الأول من 7 أرقام ، ثم رقمان من رقم واحد لكل منهما:

```
               X
\d+......\d+\d+
(1234567)(8)(9)z
```

يتكون الرقم الأول من 6 أرقام ، ثم عدد 3 أرقام:

```
             X
\d+.......\d+
(123456)(789)z
```

يتكون الرقم الأول من 6 أرقام ، ثم رقمان:

```
               X
\d+.....\d+ \d+
(123456)(78)(9)z
```

…وما إلى ذلك وهلم جرا.

هناك عدة طرق لتقسيم مجموعة من الأرقام 123456789 إلى أرقام. على وجه الدقة ، هناك 2 n ‑1 ، حيث n هو طول المجموعة.

There are many ways to split a sequence of digits 123456789 into numbers. To be precise, there are 2n-1, where n is the length of the sequence.

• For 123456789 we have n=9, that gives 511 combinations.
• For a longer sequence with n=20 there are about one million (1048575) combinations.
• For n=30 – a thousand times more (1073741823 combinations).

Trying each of them is exactly the reason why the search takes so long.

يحدث الشيء نفسه في مثالنا الأول ، عندما ننظر إلى الكلمات حسب النمط ^ (\ w + \ s؟) * $ في السلسلة مدخل معلق!.

The similar thing happens in our first example, when we look for words by pattern ^(\w+\s?)*$ in the string An input that hangs!.

The reason is that a word can be represented as one \w+ or many:

(input)
(inpu)(t)
(inp)(u)(t)
(in)(p)(ut)
...

بالنسبة للإنسان ، من الواضح أنه قد لا يكون هناك تطابق ، لأن السلسلة تنتهي بعلامة تعجب ! ، لكن التعبير العادي يتوقع حرفًا كلمة نمط: \ w أو نمطمسافة: \ s في النهاية. لكن المحرك لا يعرف ذلك.

It tries all combinations of how the regexp (\w+\s?)* can “consume” the string, including variants with spaces (\w+\s)* and without them (\w+)* (because spaces \s? are optional). As there are many such combinations (we’ve seen it with digits), the search takes a lot of time.

What to do?

Should we turn on the lazy mode?

Unfortunately, that won’t help: if we replace \w+ with \w+?, the regexp will still hang. The order of combinations will change, but not their total count.

Some regular expression engines have tricky tests and finite automations that allow to avoid going through all combinations or make it much faster, but most engines don’t, and it doesn’t always help.

كيفية الإصلاح؟

هناك طريقتان رئيسيتان لإصلاح المشكلة.

الأول هو تقليل عدد التركيبات الممكنة.

Let’s make the space non-optional by rewriting the regular expression as ^(\w+\s)*\w*$ – we’ll look for any number of words followed by a space (\w+\s)*, and then (optionally) a final word \w*.

تعادل regexp هذه السابقة (تتطابق مع نفسها) وتعمل بشكل جيد:

let regexp = /^(\w+\s)*\w*$/;
let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false

لماذا اختفت المشكلة؟

That’s because now the space is mandatory.

The previous regexp, if we omit the space, becomes (\w+)*, leading to many combinations of \w+ within a single word

So input could be matched as two repetitions of \w+, like this:

\w+  \w+
(inp)(ut)

The new pattern is different: (\w+\s)* specifies repetitions of words followed by a space! The input string can’t be matched as two repetitions of \w+\s, because the space is mandatory.

The time needed to try a lot of (actually most of) combinations is now saved.

منع التراجع

It’s not always convenient to rewrite a regexp though. In the example above it was easy, but it’s not always obvious how to do it.

Besides, a rewritten regexp is usually more complex, and that’s not good. Regexps are complex enough without extra efforts.

Luckily, there’s an alternative approach. We can forbid backtracking for the quantifier.

The root of the problem is that the regexp engine tries many combinations that are obviously wrong for a human.

على سبيل المثال في نمط regexp : (\ d +) * $ من الواضح للإنسان ، أن النمط: + لا يجب التراجع عنه. إذا استبدلنا نمطًا `` واحدًا: \ d + بنمطين منفصلين: \ d + \ d + `، فلن يتغير شيء:

`` \d+……… (123456789)!

\d+…\d+…. (1234)(56789)!

And in the original example `pattern:^(\w+\s?)*$` we may want to forbid backtracking in `pattern:\w+`. That is: `pattern:\w+` should match a whole word, with the maximal possible length. There's no need to lower the repetitions count in `pattern:\w+` or to split it into two words `pattern:\w+\w+` and so on.

Modern regular expression engines support possessive quantifiers for that. Regular quantifiers become possessive if we add `pattern:+` after them. That is, we use `pattern:\d++` instead of `pattern:\d+` to stop `pattern:+` from backtracking.

Possessive quantifiers are in fact simpler than "regular" ones. They just match as many as they can, without any backtracking. The search process without bracktracking is simpler.

هناك أيضًا ما يسمى "مجموعات الالتقاط الذري" - وهي طريقة لتعطيل التراجع داخل الأقواس.

...But the bad news is that, unfortunately, in JavaScript they are not supported.

We can emulate them though using a "lookahead transform".

### انظروا إلى الإنقاذ!

So we've come to real advanced topics. We'd like a quantifier, such as `pattern:+` not to backtrack, because sometimes backtracking makes no sense.

The pattern to take as many repetitions of `pattern:\w` as possible without backtracking is: `pattern:(?=(\w+))\1`. Of course, we could take another pattern instead of `pattern:\w`.

That may seem odd, but it's actually a very simple transform.

Let's decipher it:

- Lookahead `pattern:?=` looks forward for the longest word `pattern:\w+` starting at the current position.
- The contents of parentheses with `pattern:?=...` isn't memorized by the engine, so wrap `pattern:\w+` into parentheses. Then the engine will memorize their contents
- ...And allow us to reference it in the pattern as `pattern:\1`.

هذا هو: نحن نتطلع إلى المستقبل - وإذا كانت هناك كلمة `pattern: \ w +` ، فقم بمطابقتها كـ `pattern: \ 1`.

لماذا ا؟ ذلك لأن lookahead يعثر على كلمة `pattern: \ w +` ككل ونلتقطها في النمط بـ `pattern: \ 1`. لذا قمنا بتطبيق نمط امتلاك زائد `نمط: +` كمّي. يلتقط فقط الكلمة `نمط: \ w +` ، وليس جزءًا منها.

على سبيل المثال ، في كلمة `subject: JavaScript` ، قد لا تتطابق فقط مع` match: Java` ، ولكن تترك `match: Script` لتتطابق مع باقي النمط.

إليك مقارنة بين نمطين:

```js run
alert( "JavaScript".match(/\w+Script/)); // JavaScript
alert( "JavaScript".match(/(?=(\w+))\1Script/)); // null

1. في المتغير الأول النمط: \ w + يلتقط أولاً الكلمة الموضوع: جافا سكريبت ثمالنمط: +يتراجع حرفًا بحرف ، في محاولة لمطابقة بقية النمط ، حتى ينجح في النهاية (عندما \ w + يتطابق مع Java).
2. في المتغير الثاني النمط: (؟ = (\ w +)) يتطلع إلى الأمام ويجد كلمة الموضوع: JavaScript ، المضمنة في النمط ككل بواسطةالنمط: \ 1 ، لذلك لا يزال هناك لا توجد طريقة للعثور على “الموضوع: البرنامج النصي” بعده.

يمكننا وضع تعبير عادي أكثر تعقيدًا في النمط: (؟ = (\ w +)) \ 1 بدلاً منالنمط: \ w ، عندما نحتاج إلى منع التراجع عن النمط: + بعده.

let regexp = /^((?=(\w+))\2\s?)*$/;

alert( regexp.test("A good string") ); // true

let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false, works and fast!

هنا يُستخدم “النمط: \ 2” بدلاً من “النمط: \ 1” ، نظرًا لوجود أقواس خارجية إضافية. لتجنب العبث بالأرقام ، يمكننا تسمية الأقواس ، على سبيل المثال نمط :(؟ <word> \ w +).

// parentheses are named ?<word>, referenced as \k<word>
let regexp = /^((?=(?<word>\w+))\k<word>\s?)*$/;

let str = "An input string that takes a long time or even makes this regex hang!";

alert( regexp.test(str) ); // false

alert( regexp.test("A correct string") ); // true

تسمى المشكلة الموضحة في هذه المقالة “التراجع الكارثي”.

تناولنا طريقتين لكيفية حلها:

• أعد كتابة regexp لخفض عدد المجموعات الممكنة.
• منع التراجع.