  Modern regex languages have strayed far from well-understood traditional
regular expressions: they include features that fundamentally transform the
matching problem. In exchange for these features, modern regex engines at times
suffer from exponential complexity blowups, a frequent source of
denial-of-service vulnerabilities in JavaScript applications. Worse, regex
semantics differ across languages, and the impact of these divergences on
algorithmic design and worst-case matching complexity has seldom been
investigated.
  This paper provides a novel perspective on JavaScript's regex semantics by
identifying a larger-than-previously-understood subset of the language that can
be matched with linear time guarantees. In the process, we discover several
cases where state-of-the-art algorithms were either wrong (semantically
incorrect), inefficient (suffering from superlinear complexity) or excessively
restrictive (assuming certain features could not be matched linearly). We
introduce novel algorithms to restore correctness and linear complexity. We
further advance the state-of-the-art in linear regex matching by presenting the
first nonbacktracking algorithms for matching lookarounds in linear time: one
supporting captureless lookbehinds in any regex language, and another
leveraging a JavaScript property to support unrestricted lookaheads and
lookbehinds. Finally, we describe new time and space complexity tradeoffs for
regex engines. All of our algorithms are practical: we validated them in a
prototype implementation, and some have also been merged in the V8 JavaScript
implementation used in Chrome and Node.js.
