Simon Willison's Weblog: regular-expressions

tc39/proposal-regex-escaping

2025-02-18T21:53:56+00:00

I just heard from Kris Kowal that this proposal for ECMAScript has been approved for ECMA TC-39:

Almost 20 years later, @simon’s RegExp.escape idea comes to fruition. This reached “Stage 4” at ECMA TC-39 just now, which formalizes that multiple browsers have shipped the feature and it’s in the next revision of the JavaScript specification.

I'll be honest, I had completely forgotten about my 2006 blog entry Escaping regular expression characters in JavaScript where I proposed that JavaScript should have an equivalent of the Python re.escape() function.

It turns out my post was referenced in this 15 year old thread on the esdiscuss mailing list, which evolved over time into a proposal which turned into implementations in Safari, Firefox and soon Chrome - here's the commit landing it in v8 on February 12th 2025.

One of the best things about having a long-running blog is that sometimes posts you forgot about over a decade ago turn out to have a life of their own.

Tags: blogging, ecmascript, javascript, regular-expressions, standards

Why I invented "dash encoding", a new encoding scheme for URL paths

2022-03-05T21:50:38+00:00

Datasette now includes its own custom string encoding scheme, which I've called dash encoding. I really didn't want to have to invent something new here, but unfortunately I think this is the best solution to my very particular problem. Some notes on how dash encoding works and why I created it.

Update 18th March 2022: This turned out not to be the right idea for my project after all! I ended up settling on a Tilde encoding scheme instead.

Table names and rows in URLs

I've put a lot of thought into the design of Datasette's URLs.

Datasette exposes relational databases tables, as both web pages and a JSON API.

Consider a database in a SQLite file called legislators.db, containing a table called legislator_terms (example from this tutorial). The URL path to the web interface for that table will be:

/legislators/legislator_terms

And the JSON API will be here:

/legislators/legislator_terms.json

(Worth noting that Datasette supports other formats here too - CSV by default, and plugins can add more formats such as GeoJSON or Atom or iCal.)

Datasette also provides pages (and APIs) for individual rows, identified by their primary key:

For tables with compound primary keys, these pages can include the primary key values separated by commas:

/fixtures/compound_three_primary_keys/a,a,a

This is all pretty straightforward so far. But now we get to the challenge: what if a table's name or a row's primary key contains a forward slash or a period character?

This could break the URL scheme!

SQLite table names are allowed to contain almost any character, and Datasette is designed to work with any existing SQLite database - so I can't guarantee that a table with one of those characters won't need to be handled.

Consider a database with two tables - one called legislator_terms and another called legislator_terms/1 - given the URL /legislators/legislator_terms/1 it's no longer clear if it refers to the table with that name or the row with primary key 1 in the other table!

A similar problem exists for table names with as legislators.csv - which end in a format. Or primary key string values that end in .json.

Why URL encoding doesn't work here

Up until now, Datasette has solved this problem using URL percent encoding. This provides a standard mechanism for encoding "special" characters in URLs.

legislator_terms/1 encodes to legislator_terms%2F1

This should be enough to solve the problem. The URL to that weirdly named table can now be:

/legislators/legislator_terms%2F1

When routing the URL, the application can take this into account and identify that this it a table named legislator_terms/1, as opposed to a request for the row with ID 1 in the legislator_terms table.

There are two remaining problems.

Firstly, the "." character is ignored by URL encoding, so we still can't tell the difference between /db/table.json and a table called table.json. I worked around this issue in Datasette by supporting an optional alternative ?_format=json parameter, but it's messy and confusing.

Much more seriously, it turns out there are numerous common pieces of web infrastructure that "helpfully" decode escaped characters in URLs before passing them on to the underlying web application!

I first encountered this in the ASGI standard itself, which decoded characters in the path field before they were passed to the rest of the application.I submitted a PR adding raw_path to ASGI precisely to work around this problem for Datasette.

Over time though, the problem kept cropping up. Datasette aims to run on as many hosting platforms as possible. I've seen URL escaping applied at a higher level enough times now to be very suspicious of any load balancer or proxy or other web server mechanism that might end up executing between Datasette and the rest of the web.

Update: Flask core maintainer David Lord confirms on Twitter that this is a long-standing known problem:

This behavior in Apache/nginx/etc is why WSGI/ASGI can't specify "literal URL the user typed in", because anything in front of the app might modify slashes or anything else. So all the spec can provide is "decoded URL".

So, I need a way of encoding a table name that might include / and . characters in a way that will survive some other layer of the stack decoding URL encoded strings in the URL path before Datasette gets to see them!

Introducing dash encoding

That's where dash encoding comes in. I tried to design the fastest, simplest encoding mechanism I could that would solve this very specific problem.

Loose requirements:

Reversible - it's crucial to at any possible value survives a round-trip through the encoding
Avoid changing the string at all if possible. Otherwise I could use something like base64, but I wanted to keep the name in the URL as close to readable as possible
Survive interference by proxies and load balancer that might try to be helpful
Fast to apply the transformation
As simple as possible
Easy to implement, including in languages other than Python

Dash encoding consists of three simple steps:

Replace all single hyphen characters - with two hyphens --
Replace any forward slash / character with hyphen forward slash -/
Replace any period character . with hyphen period -.

To reverse the encoding, run those steps backwards.

Here the Python implementation of this encoding scheme:

def dash_encode(s: str) -> str:
     "Returns dash-encoded string - for example ``/foo/bar`` -> ``-/foo-/bar``"
     return s.replace("-", "--").replace(".", "-.").replace("/", "-/")

def dash_decode(s: str) -> str:
     "Decodes a dash-encoded string, so ``-/foo-/bar`` -> ``/foo/bar``"
     return s.replace("-/", "/").replace("-.", ".").replace("--", "-")

And the pytest tests for it:

@pytest.mark.parametrize(
     "original,expected",
     (
         ("abc", "abc"),
         ("/foo/bar", "-/foo-/bar"),
         ("/-/bar", "-/---/bar"),
         ("-/db-/table---.csv-.csv", "---/db---/table-------.csv---.csv"),
     ),
 )
 def test_dash_encoding(original, expected):
     actual = utils.dash_encode(original)
     assert actual == expected
     # And test round-trip
     assert original == utils.dash_decode(actual)

Here's the full commit.

This meets my requirements.

Capturing these with a regular expression

There was one remaining challenge. Datasette uses regular expressions - inspired by Django - to route requests to the correct page.

I wanted to use a regular expression to extract out dash encoded values, that could also distinguish them from / and - and . characters that were not encoded in that way.

Here's the pattern I came up with for strings matching this pattern:

([^\/\-\.]*|(\-/)|(\-\.)|(\-\-))*

Broken down:

[^\/\-\.]* means 0 or more characters that are NOT one of . or / or - - since we don't care about those characters at all
(\-/) means the explicit sequence -/
(\-\.) means the explicit sequence -.
(\-\-) means the explicit sequence --
Those four are wrapped in a group combined with the | or operator
The group is then wrapped in a (..)* - specifying that it can repeat as many times as you like

A better way to break down this regular expression is visually, using Debuggex:

Combining this into the full regular expression that matches a /database/table.format path is even messier, due to the need to add non-capturing group syntax (?:..) and named groups (?P<name>...) - it ends up looking like this:

^/(?P<database>[^/]+)/(?P<table>(?:[^\/\-\.]*|(?:\-/)*|(?:\-\.)*|(?:\-\-)*)*?)\.(?P<format>\w+)?$

Visualized with Debuggex:

Update: Thanks to suggestions from Matthew Somerville I simplified this further to:

^/(?P<database>[^/]+)/(?P<table>[^\/\-\.]*|\-/|\-\.|\-\-)*(?P<format>\.\w+)?$

Next steps: implementation

I'm currently working on integrating it into Datasette in this PR. The full history of my thinking around this problem can be found in issue 1439, with comments stretching back to August last year!

Tags: regular-expressions, urls, datasette

The unexpected Google wide domain check bypass

2020-03-09T23:27:41+00:00

The unexpected Google wide domain check bypass

Fantastic story of discovering a devious security vulnerability in a bunch of Google products stemming from a single exploitable regular expression in the Google closure JavaScript library.

Via Hacker News

Tags: regular-expressions, security

Details of the Cloudflare outage on July 2, 2019

2019-07-12T17:36:25+00:00

Details of the Cloudflare outage on July 2, 2019

Best retrospective I’ve read in a long time. The outage was caused by a backtracking regex rule that was added to the Web Application Firewall project, which rolls out globally and skips most of Cloudflare’s regular graduar rollout process (delightfully animal themed, named DOG for the dogfooding PoP that their employees use, PIG for the Guinea Pig PoPs reserved for free customers, then Canary for the final step) so that they can deploy counter-measures to newly discovered vulnerabilities as quickly as possible—but the real value in the retro is that it provides an extremely deep insight into how Cloudflare organize, test and manage their changes. Really interesting stuff.

Via Hacker News

Tags: operations, regular-expressions, cloudflare, postmortem

r1chardj0n3s/parse: Parse strings using a specification based on the Python format() syntax.

2018-02-25T16:58:32+00:00

r1chardj0n3s/parse: Parse strings using a specification based on the Python format() syntax.

Really neat API design: parse() behaves almost exactly in the opposite way to Python’s built-in format(), so you can use format strings as an alternative to regular expressions for extracting specific data from a string.

Via requests-html/Pipfile

Tags: python, regular-expressions

A Regular Expression Matcher: Code by Rob Pike, Exegesis by Brian Kernighan

2017-12-05T18:36:12+00:00

A Regular Expression Matcher: Code by Rob Pike, Exegesis by Brian Kernighan

Delightfully clear and succinct 30-line C implementation of a regular expression matcher that supports $, ^, . and * operations.

Via Hacker News

Tags: c, regular-expressions, rob-pike

Escaping regular expression characters in JavaScript (updated)

2010-07-04T18:23:00+00:00

Escaping regular expression characters in JavaScript (updated)

The JavaScript regular expression meta-character escaping code I posted back in 2006 has some serious flaws—I’ve just posted an update to the original post.

Tags: escaping, javascript, regular-expressions, recovered

Quoting Andrew Clover

2009-11-16T10:32:15+00:00

Every time you attempt to parse HTML with regular expressions, the unholy child weeps the blood of virgins, and Russian hackers pwn your webapp. Parsing HTML with regex summons tainted souls into the realm of the living. HTML and regex go together like love, marriage, and ritual infanticide.

— Andrew Clover

Tags: andrew-clover, funny, html, parsing, regex, regular-expressions, stackoverflow, xhtml

Django security updates released

2009-10-10T00:24:59+00:00

Django security updates released

A potential denial of service vulnerability has been discovered in the regular expressions used by Django form library’s EmailField and URLField—a malicious input could trigger a pathological performance. Patches (and patched releases) for Django 1.1 and Django 1.0 have been published.

Tags: denial-of-service, django, python, regular-expressions, security

Introducing Yardbird

2009-05-22T23:13:39+00:00

Introducing Yardbird

I absolutely love it—an IRC bot built on top of Twisted that passes incoming messages off to Django code running in a separate thread. Requests and Response objects are used to represent incoming and outgoing messages, and Django’s regex-based URL routing is used to dispatch messages to different handling functions based on their content.

Tags: django, irc, regular-expressions, threads, twisted, yardbird

Escaping regular expression characters in JavaScript

2006-01-20T12:19:13+00:00

JavaScript's support for regular expressions is generally pretty good, but there is one notable omission: an escaping mechanism for literal strings. Say for example you need to create a regular expression that removes a specific string from the end of a string. If you know the string you want to remove when you write the script this is easy:

var newString = oldString.replace(/Remove from end$/, '');

But what if the string to be removed comes from a variable? You'll need to construct a regular expression from the variable, using the RegExp constructor function:

var re = new RegExp(stringToRemove + '$');
var newString = oldString.replace(re, '');

But what if the string you want to remove may contain regular expression metacharacters - characters like $ or . that affect the behaviour of the expression? Languages such as Python provide functions for escaping these characters (see re.escape); with JavaScript you have to write your own.

Here's mine:

RegExp.escape = function(text) {
  if (!arguments.callee.sRE) {
    var specials = [
      '/', '.', '*', '+', '?', '|',
      '(', ')', '[', ']', '{', '}', '\\'
    ];
    arguments.callee.sRE = new RegExp(
      '(\\' + specials.join('|\\') + ')', 'g'
    );
  }
  return text.replace(arguments.callee.sRE, '\\$1');
}

This deals with another common problem in JavaScript: compiling a regular expression once (rather than every time you use it) while keeping it local to a function. argmuments.callee inside a function always refers to the function itself, and since JavaScript functions are objects you can store properties on them. In this case, the first time the function is run it compiles a regular expression and stashes it in the sRE property. On subsequent calls the pre-compiled expression can be reused.

In the above snippet I've added my function as a property of the RegExp constructor. There's no pressing reason to do this other than a desire to keep generic functionality relating to regular expression handling the same place. If you rename the function it will still work as expected, since the use of arguments.callee eliminates any coupling between the function definition and the rest of the code.

Update 18th Feb 2025: 19 years after I published this RegExp.escape() has made it into the language!

Tags: escaping, javascript, regular-expressions

"sexeger"[::-1]

2003-09-17T01:53:18+00:00

Via Ned Batchelder, an article on Reversing Regular Expressions from Perl.com. Otherwise known as Sexeger, these offer a performance boost over normal regular expressions for certain tasks. The basic idea is pretty simple: searching backwards through a string using a regular expression can be a messy business, but by reversing both the string and the expression, running it, then reversing the result far better performance can be achieved (reversing a string is a relatively inexpensive operation). The example code is in Perl, but I couldn't resist trying it in Python. The challenge is to find the last number occurring in a string.

>>> import re
>>> lastnum = re.compile(r'(\d+)(?!\D*\d)')
>>> s = ' this isa 454 asd very very 
  very long strin9 asd9 009 76 with numbers 
  99 in it and here is the last 537 number'
  # NB this was all on one line originally
>>> lastnum.search(s).group(0)
'537'
>>> import timeit
>>> t1 = timeit.Timer('lastnum.search(s).group(0)', 
         'from __main__ import lastnum, s')
>>> print "%.2f usec/pass" % (1000000 * t1.timeit(number=100000)/100000)
26.82 usec/pass
>>> lastnumrev = re.compile('(\d+)')
>>> lastnumrev.search(s[::-1]).group(0)[::-1]
'537'
>>> t2 = timeit.Timer('lastnumrev.search(s[::-1]).group(0)[::-1]', 
         'from __main__ import lastnumrev, s')
>>> print "%.2f usec/pass" % (1000000 * t2.timeit(number=100000)/100000)
9.26 usec/pass

There are a few points worth explaining in the above code. The (?!\D*\d) part of the first regular expression is a negative lookahead assertion - it basically means "match the subpattern provided it isn't followed by a string of non-digits followed by at least one digit. This is the bit that ensures we only get back the last digit in the string, and is also the bit that could cause a performance problem.

'some string'[::-1] is an example of Extended Slices, introduced in Python 2.3. Its affect is to reverse the string, by stepping through it from start to end going back one character at a time.

The actual benchmarking code makes use of the new timeit module from Python 2.3 - I copied it verbatim from that module's example section in the manual.

The results speak for themselves: 26.82 for the lookahead assertion expression compared to just 9.26 for the reversed regular expression. This is definitely a useful trick to add to the tool box.

Tags: python, regular-expressions

Verbose Regular Expressions

2003-04-11T03:01:15+00:00

Ned Batchelder describes Verbose Python regular expressions. This is one of the things I've known about (as in known that they exist) for ages but have never got around to using. I've been working with some pretty heavy regular expressions recently that could really do with the clarity of being defined in verbose format with comments.

PHP also has support for verbose REs, thanks to the excellent pcre functions. Just use the 'x' modifier as explained on this manual page.

Tags: ned-batchelder, php, python, regular-expressions