Wednesday, 13 February 2019

Variable-Length Lookbehinds: actually possible in Perl/PCRE!

Get strapped in, because this is as close as you're going to get to breaking news in the world of regular expressions.



You know what the best thing is about being involved in regex circles? It's not the money or the fame or the women.. no no; it's that, on occasion, you get to witness incredible discoveries unfold before your very eyes. This is exactly what happened in a small StackExchange chatroom earlier, when fellow regex tinkerer Grimy cracked a problem that previously seemed insoluble. In doing so, he uncovered a technique for emulating a feature that has been coveted for years by Perl and PCRE users alike: variable-length lookbehinds.

Now, forget \K. That doesn't come close to having the expressive power we want. I'm talking about truly emulating variable-length lookbehinds; that is, doing so for all conceivable scenarios.

The Revelation


In response to a challenge to match an arbitrary string (in the domain of ^.*$) that contains no unique characters, a task I once dismissed as impossible in the general case, Grimy ingeniously came up with the following:

Wonderfully elegant and simple in principle. Let us begin by examining the core concept.

The Concept

((?<=(?= ... |(?3)).))
The trick is to remember that, while lookbehinds can only peek a fixed number of characters behind the current matching point, the lookaheads they contain are not subject to any such restriction. If \1 is a single character, (?<=(?=\1).) succeeds where (?<=\1) fails because in the former case you are telling the regex engine that it needs to go back precisely one character to look for \1.

Because recursive algorithms are tricky to follow, let us expand this subexpression a couple of levels deep to observe what's happening:
((?<=(?= ... |(?<=(?= ... |(?<=(?= ... |(?3)).)).)).))
Notice how we're moving back one character each step of the way. So if (?= ... ) fails to match, move back one character and try again. Thus, it is equivalent in essence to using (?<=(?= ...).*) if actual variable-length lookbehinds were possible.

The Nanny


If you've read and understood everything so far, you may have thought to look back at Grimy's original expression to try and understand it in full. What, then, you ask, is the purpose of \n in the lookahead? After all, \n, which matches a new-line character, should not exist in the domain of ^.*$ since `.` does not match a new-line by default. So why is it there?

Regex engines often have a bunch of nannies in place to prevent you from hurting yourself. One of these employed by PCRE is a compile-time check for recursive calls that appear, from a cursory static inspection, as though they may not terminate. The simplest example of this is the expression (?R), which yields the compile-time error:
40  recursive call could loop indefinitely
With Grimy's expression, the PCRE engine doesn't realize that \2 is guaranteed to match a single character. To work around this, we need to give the engine at least one non-empty path to follow. \n is a contradiction in the domain of ^.*$ and, more importantly, it functions as a non-empty alternative that convinces the nanny that we know what we're doing.

Note that in the more general domain of ^[\s\S]*$, which may include new-line characters, x^ serves as a non-empty contradiction.

The Emulation


Perspicacious readers may have observed that the method above involves an unbounded lookahead, one that may peer far past the position at which we wish to place our emulated lookbehind. This is fine for the problem it aimed to solve, but if we want to expand the method to work in the general case, this issue needs to be addressed.

And so, for a variable-length subexpression X, (?<=X) can be implemented in both Perl and PCRE as:
(?=(?'a'[\s\S]*))(?'b'X(?=\k'a'\z)|(?<=(?=x^|(?&b))[\s\S]))
See it in action on regex101

To negate it and emulate (?<!X), simply enclose the whole thing in a negative lookahead:
(?!(?=(?'a'[\s\S]*))(?'b'X(?=\k'a'\z)|(?<=(?=x^|(?&b))[\s\S])))
Aside from the fact that I've used two capturing groups, that snippet is basically plug-and-play: you may insert it anywhere in your expression where a variable-length lookbehind is desired.

The main difference here is that a new group "a" has been added to capture the portion of the string after the current matching point, so that when we travel backwards and look ahead for X we know where to stop. This solves the issue mentioned above.

Next, X has been moved to the outer group "b" as it would fail to match if X were zero-width since the lookahead only begins at the position one character behind the current matching point, and only moves backwards thereafter.

Here is a breakdown of the various components:
(?=(?'a'[\s\S]*))  # Capture the rest of the string in "a"
(?'b'
  X(?=\k'a'\z)     # Match X followed by the contents of "a" to ensure
                   # the emulated lookbehind stops at the correct point.
  |                # OR
  (?<=             # Look behind (one character) match either:
    (?=
      x^           # A contradiction; non-empty to appease the nanny
      |            # OR
      (?&b)        # Recurse (match X OR look behind (one character)) etc..
    )
    [\s\S]         # How far we go back each step: one single character
  )
) 

Note that by emulating a positive lookbehind in this way, you lose the luxury of having capture groups in X that return their values to the caller. But are you complaining?

The End


There you have it: another impossibility made possible by the creative application of old tools. I hope you enjoy using this new toy as much as I certainly will. Big shout out once again to Grimy for his stroke of genius.

As usual, I welcome you to follow me on twitter to stay apprised of more regex wackiness in the future.

The Bonus


What about problems that require comparing the substring at the current matching point to multiple substrings at later positions in the string - can we now handle those? Turns out we can! By iterating forwards with a lookahead and using our new toy to look back to the original matching point, we can make short work of any problem of that nature. For example, "match the longest word in a line" can now be solved in the general case:
\b(\w++)(?=(.*))(?!(.*\W)\b((?<=(?=(?=\1\2$)(?:(?=\w*+\3(\5?+\w))\w)++\b|(?4)).)))
Figuring out how that works is left as an exercise to the reader :) Suffice it to say, there is now a whole new set of problems for which we can irresponsibly abuse regex.

35 comments:

  1. I have to search sites with relevant information on given topic and provide them to teacher our opinion and the article.
    ExcelR digital marketing courses in mumbai

    ReplyDelete
  2. Our service has been very supportive to our customers and especially in solving their problems and providing them with best boxes which are fully credible and worthy of their trust.
    Custom Boxes Wholesale,

    Paper Cigarette Boxes,

    Bath bomb packaging,

    Pre Roll Packaging,

    Cardboard Cigarette boxes,

    Blank Cigarette Boxes,

    custom burger boxes

    french fries boxes,

    ReplyDelete
  3. keep up the good work. this is an Ossam post. This is to helpful, i have read here all post. i am impressed. thank you. this is our courses in data analytics
    courses in data analytics | https://www.excelr.com/data-analytics-certification-training-course-in-mumbai

    ReplyDelete
  4. In the present days a large number of candidates are showing interest towards the sarkari result 10+2 latest job. By applying for the various positions candidates are attending for the competitive exams conducting by the various government organizations

    ReplyDelete
  5. Are you looking for data structure assignment help? Are
    you unable to find best experts? Perfect, you landed at
    the right page. “Assignment help website” is one of the
    oldest assignment help providers whose aim is to help
    students with quality and affordable data structure
    assignments.

    ReplyDelete
  6. Ducat provides best java training institute in noida as per the current industry standards. Our training programs will enable professionals to secure placements in MNCs. We are providing our world-class training facilities for all the students who want to become professional java developer.
    https://www.ducatindia.com/cloudcomputingtraining/

    ReplyDelete
    Replies
    1. Amazing Article. Candidates who are eager to get the FreeJobAlert . they can get the all information from this page. The Candidates have to visit our website Sarkari Result .
      Also Candidates Can Get Jobs in India Post Office Post Office Recruitment

      Delete
  7. Really Very helpful Post & thanks for sharing & keep up the good work.
    Oflox Is The Best Digital Marketing Company In Dehradun Or Website Design Company In Dehradun

    ReplyDelete
  8. Human emotions can be tricky. But It can't be tough to handle, One of those emotions is anger. Let me explain Extreme anger can affect your life in unthinkable ways. Do you have anger issues? If your answer is yes! Get help from MyFloridaGreen they offers medical marijuana card Sarasota , medical marijuana card Saint petersburg , Medical marijuana card naples.

    ReplyDelete
  9. iCustomBoxes are exceptionally well known among blessing packaging products. These Pillow Boxes are extremely attractive in their standpoint and can fill the need of blessing Pillow Boxes packaging in a novel and smart manner. They can be redone as per prerequisites and can be printed with boundless brightening print styles.
    Custom Boxes

    ReplyDelete
  10. This comment has been removed by the author.

    ReplyDelete
  11. Thank you for your outstanding article. I will be your regular visitor. Are you experiencing difficulty in writing business analytics? Well, you don’t have to experience sleepless nights because of business analytics assignments. At our Business Management Assignment Help Service, we have experienced business analytics writers who can provide you with the much-needed help in writing your assignments. Visit Business Analytics Assignment Help. for more

    ReplyDelete
  12. Garmin.com/express Garmin.com/Express Download Garmin Express To Install & Manage Garmin Updates For all Garmin Devices With Easy Instruction by visiting garmin.com/express.

    ReplyDelete
  13. Mywifiext Mywifiext.net Login, Follow the step by step guidelines for Mywifiext.net Login, account setup and configure your Netgear Extender to experience seamless connectivity.

    ReplyDelete
  14. TurboTax Sign inTurboTax Login - Now you may Sign in to Your TurboTax Online account to start, continue, or amend a tax return, check the e-file and many more

    ReplyDelete
  15. Rand Mcnally Dock Update Rand McNally is a world-leader in providing GPS based Navigation Devices. Its innovative product range covers the diverse needs of various users. These intuitive, user-friendly devices are designed to eliminate stressful navigation out of your travels. However,

    ReplyDelete
  16. office.com/setup office.com/setup - For Office Setup and Activation go to www.office.com/setup and get started with activation and installation by entering product key.

    ReplyDelete
  17. Garmin.com/express Garmin express - Register, update and sync your device with Garmin. Manage devices from your desktop. Garmin Express is a computer application.

    ReplyDelete
  18. Magellan Gps Update Magellan Gps Update is a prominent portable GPS navigation consumer electronics company. To take the benefits of the Magellan GPS device, the users have to install and get the latest Magellan GPS updates. Through the GPS Magellan updates, the user can have an up-to-date version of the GPS device. In the year 1986, the company was established, and the Head Quarter is in San Dimas, California.

    ReplyDelete
  19. Very Nice Tips. Currently, there is a national Lock down in Nigeria, Once the effect of COVID-19 has been cushion, JAmbites are expected to know that schools would start releasing their Post UTME Forms, so all students are advised to grab a free copy of Post UTME Past Questions and Answers on Studydriler.com.



    ReplyDelete
  20. What do you comprehend by the importance of legitimate time the board in your life? Time shows you how to play out each undertaking in the best method to accomplish the chose objectives. At the point when you begin to chip away at any undertaking, you will have a few goals to seek after as its outcome. What's more, when you are thinking to achieve your scholarly errands, you will feel the requirement for an opportunity to complete it valuable. In the event that you need to spare your time and don't wish to compose your schoolwork, take the assistance of Assignment Helper and finish your work on schedule. Specialists of task composing administrations are limited to offer beneficial "Assignment Help In US" to support researchers and spare their time. You won't get any quality issues while getting your request from expert's hands.
    visit:
    online coursework help
    online coursework writing
    coursework assignment help
    online coursework service
    coursework help online
    coursework writing service

    ReplyDelete
  21. I high appreciate this post. It’s hard to find the good from the bad sometimes, but I think you’ve nailed it! would you mind updating your blog with more information?

    Private Tutor

    Online Tutoring Services UK

    ReplyDelete
  22. Here are the list of best Advertising Agency Riyadh, Branding Agency Riyadh & Marketing Agency In Riyadh. Click and you can check the details from the word which you love to know.

    ReplyDelete
  23. Thanks for Sharing this article, I really impress your work.
    custom book boxes

    ReplyDelete
  24. Thanks for Sharing This Article.It is very so much valuable content. I hope these Commenting lists will help to my website
    servicenow online training
    best servicenow online training
    top servicenow online training

    ReplyDelete
  25. Use Homework help to connect with American academic writers in just a few minutes. Students can take online homework writing services in America when they have no one to ask their queries and find it tough to write your academic papers.

    ReplyDelete
  26. This is very useful website, this article is really helpful thank you so much for
    sharing this great knowledge Assignment Help

    ReplyDelete
  27. Students seek our online assignment help from experienced and talented academic writers for their assignments to be completed within the allotted time frame and in accordance with the required standards. If you are stuck with your research projects, essays, case studies, business reports or need Urgent Assignment Help, then MyAssignmentHelp is the place to be.

    ReplyDelete
  28. Computer Assignment writing is the task which frequently gives students a tension. If you are going through from the same. Then in such situation, you can choose our computer network assignment help service and can get a quality assignment written from us.

    ReplyDelete
  29. wonderful article. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article resolved my all queries. keep it up.
    data analytics course in Bangalore

    ReplyDelete
  30. Really nice and interesting post. I was looking for this kind of information and enjoyed reading this one. Keep posting. Thanks for sharing.....bangalore digital marketing course

    ReplyDelete
  31. Our service has been very supportive to our customers and especially in solving their problems and providing them with best Pre Roll Packaging which are fully credible and worthy of their trust.

    ReplyDelete
  32. Australian Assignment Help is best in providing cheap assignment help in Australia to students and Student Life Saviour delivers quality assignment help in Ireland to students at reasonable prices.

    ReplyDelete