Matching two words near each other is a fairly straightforward task. After all, there are only two possible ways to order them. But what if you want to match three words in any order? Now there are six possible orders (see Example 5-1). The number of ways you can shift a given set of words around is n!, or the product of consecutive integers 1 through n (“n factorial”). With four words, there are 24 possible ways to order them. By the time you get to 10 words, the number of arrangements explodes into the millions. It is simply not viable to match more than a few words near each other using the regular expression techniques discussed so far.

One way to solve this problem is by repeating a group that matches the required words or any other word (after a required word has been matched), and then using conditionals to prevent a match attempt from finishing successfully until all of the required words have been matched. Following is an example of matching three words in any order with up to five other words separating them:

(?:(?>(word1)|(word2)|(word3)|(?(1)|(?(2)|(?(3)|(?!))))w+)W*?){3,8}↵
(?(1)(?(2)(?(3)|(?!))|(?!))|(?!))

Two values:
    [ 12, 21 ]
    = 2 possible arrangements

Three values:
    [ 123, 132,
      213, 231,
      312, 321 ]
    = 6 possible arrangements

Four values:
    [ 1234, 1243, 1324, 1342, 1423, 1432,
      2134, 2143, 2314, 2341, 2413, 2432,
      3124, 3142, 3214, 3241, 3412, 3421,
      4123, 4132, 4213, 4231, 4312, 4321 ]
    = 24 possible arrangements

Factorials:
    2! = 2 × 1                                   =       2
    3! = 3 × 2 × 1                               =       6
    4! = 4 × 3 × 2 × 1                           =      24
    5! = 5 × 4 × 3 × 2 × 1                       =     120
    ⋮
    10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3628800

Here again is the regex, except that the atomic group (see Recipe 2.14) has been replaced by a standard, noncapturing group. This adds support for Python at the cost of some efficiency:

(?:(?:(word1)|(word2)|(word3)|(?(1)|(?(2)|(?(3)|(?!))))w+)W*?){3,8}↵
(?(1)(?(2)(?(3)|(?!))|(?!))|(?!))

The ‹{3,8}› quantifiers in the regular expressions just shown account for the three required words, and thus allow zero to five words in between them. The empty negative lookaheads, which look like ‹(?!)›, will never match and are therefore used to block certain paths through the regex until one or more of the required words have been matched. The logic that controls these paths is implemented using two sets of nested conditionals. The first set prevents matching any old word using ‹w+› until at least one of the required words have been matched. The second set of conditionals at the end forces the regex engine to backtrack or fail unless all of the required words have been matched.

That’s the brief overview of how this works, but rather than getting further into the weeds and describing how to add additional required words, let’s take a look at an improved implementation that adds support for more regex flavors, and involves a bit of a trick.

The ugly solution works, but it could probably win a regex obfuscation contest for being so difficult to read and manage. It would only get worse if you added more required words into the mix.

Fortunately, there’s a regular expression hack you can use that makes this a lot easier to follow, while also adding support for Java and Ruby (neither of which supports conditionals).

(?:(?>word1()|word2()|word3()|(?>1|2|3)w+)W*?){3,8}123

(?:(?:word1()|word2()|word3()|(?:1|2|3)w+)W*?){3,8}123

Using this construct, it’s easy to add more required words. Here’s an example that allows four required words to appear in any order, with a total of up to five other words between them:

(?:(?>word1()|word2()|word3()|word4()|↵
(?>1|2|3|4)w+)W*?){4,9}1234

(?:(?:word1()|word2()|word3()|word4()|↵
(?:1|2|3|4)w+)W*?){4,9}1234

These regular expressions intentionally use empty capturing groups after each of the required words. Since any attempt to match a backreference such as ‹1› will fail if the corresponding capturing group has not yet participated in the match, backreferences to empty groups can be used to control the path a regex engine takes through a pattern, much like the more verbose conditionals we showed earlier. If the corresponding group has already participated in the match attempt when the engine reaches the backreference, it will simply match the empty string and move on.

Here, the ‹(?>1|2|3)› grouping prevents matching a word using ‹w+› until at least one of the required words has been matched. The backreferences are repeated at the end of the pattern to prevent any match from successfully completing until all of the required words have been found.

Python does not support atomic groups, so once again the examples that list Python among the regex flavors replace such groups with standard noncapturing groups. Although this makes the regexes less efficient, it doesn’t change what they match. The outermost grouping cannot be atomic in any flavor, because in order for this to work, the regex engine must be able to backtrack into the outer group if the backreferences at the end of the pattern fail to match.

Even though JavaScript supports all the syntax used in the Python versions of this pattern, it has two behavioral rules that prevent this trick from working like the other flavors. The first issue is what is matched by backreferences to capturing groups that have not yet participated in a match. The JavaScript specification dictates that such backreferences match the empty string, or in other words, they always match successfully. In just about every other regular expression flavor, the opposite is true: they never match, and as a result they force the regex engine to backtrack until either the entire match fails or the group they reference participates, thereby providing the possibility that the backreference too will match.

The second difference with the JavaScript flavor involves the value remembered by capturing groups nested within a repeated, outer group—for example, ‹((a)|(b))+›. With most regex flavors, the value remembered by a capturing group within a repeated grouping is whatever the group matched the last time it participated in the match. So, after ‹(?:(a)|(b))+› is used to match ab, the value of backreference 1 would be a. However, according to the JavaScript specification, the value of backreferences to nested groups is reset every time the outer group is repeated. Hence, ‹(?:(a)|(b))+› would still match ab, but backreference 1 after the match is complete would reference a nonparticipating capturing group, which in JavaScript would match an empty string within the regex itself and be returned as undefined in, for example, the array returned by the regexp.exec() method.

Either of these behavioral differences found in the JavaScript regex flavor are enough to prevent emulating conditionals using empty capturing groups, as described here.