> I can generate the regexp ((^\/foo\/bar$)|(^\/foo\/bar\/\d+$))

And how would you know which one got matched? The regex match isn't going to tell you that. Also, it needs to recognize if multiple were matched, which is definitely not going to be done by the built-in regex matcher.

It's certainly possible, but pretending it's trivial isn't helping, either.

For more concrete syntax, consider the following Python:

  >>> import re
  >>> route = re.compile(r'(?P<fb>^/foo/bar$)|(?P<fbd>^/foo/bar/\d+$)')
  >>> route.match('/foo/bar').groupdict()
  {'fb': '/foo/bar', 'fbd': None}
  >>> route.match('/foo/bar/1').groupdict()
  {'fb': None, 'fbd': '/foo/bar/1'}

If the fb group is set, act on the first route. If the fbd group is set, act on the second.

I know very little of NFAs/DFAs/FSMs, or even string parsing in general, but a year ago I built a URL matching engine using exactly this method in Python, in combination with Google's RE2 library (https://code.google.com/p/re2/). It was far faster than anything else I experimented with, and RE2 also improved the speed dramatically by eliminating backtracking.

Nice to know that what I made is considered the best solution algorithmically.

You can check the 2nd and 3rd groups when using /(^\/foo\/bar$)|(^\/foo\/bar\/\d+$)/:

    > /(^\/foo\/bar$)|(^\/foo\/bar\/\d+$)/.exec('/foo/bar')
    [ '/foo/bar',
      '/foo/bar',
      undefined,
      index: 0,
      input: '/foo/bar' ]

    > /(^\/foo\/bar$)|(^\/foo\/bar\/\d+$)/.exec('/foo/bar/3')
    [ '/foo/bar/3',
      undefined,
      '/foo/bar/3',
      index: 0,
      input: '/foo/bar/3' ]

EDIT: Markdown differences.

First off, you don't need to handle the 'multiple' case, since the "|" has precedence rules applied to it. The leftmost match is the match. Second, you know which one matched based on the index of the capture groups, which is deterministic. See this example: http://rubular.com/r/HiW6gjnURe

You could write a simple router based on this in < 50 lines of JS. I'd do it now, but I have work to do.

> First off, you don't need to handle the 'multiple' case, since the "|" has precedence rules applied to it.

Read my top-level post again - multiple routes can be called on the same request, so express has to be able to find all of the matches, not just the first one. This is a mistake in the original article, as the author doesn't appear to understand the power of express routers.

> Second, you know which one matched based on the index of the capture groups, which is deterministic.

Deterministic, yes. But now you're also writing your own regex parser, because you have to know how many capture groups each sub-regex contains in order to figure out the indexing.

Ah, I did miss that, but it does still work. Run the following code below, you'll see multiple groups match.

    "/foo/bar/3".match(/((^\/foo\/bar\/.*)|(^\/foo\/bar\/(\d+)$)|(^\/baz))/) => 

Additionally, parsing out the number of capture groups in a regexp is simple, just looked for unescaped paren groups. You can do it once at route definition.

> just looked for unescaped paren groups

Don't forget non-matching groups! Which brings up my point yet again - everyone is pretending this is a dead-simple problem to solve, but all of the proposed solutions are buggy. Not really an option for such a widely-used library.

I'm not claiming it's impossible. I'm claiming it's more difficult than anyone is willing to admit.

Counting capturing groups is a solved problem - http://stackoverflow.com/questions/16046620/regex-to-count-t...

Actually, no: if you run this you will see three matching groups, but the first is always the whole match (this is in addition to the capture groups that are defined), the second is the (redundant) capture group you put around the whole thing, and the third is foo/bar/.*. /foo/bar/\d+ is not matched at all, even though it matches the input string.

You are 100% correct, I forgot about that extra group (that doesn't need to be there).

That being said, most frameworks don't have multiple matching routes, and I can't imagine that many people miss them. I've never used a framework that supported that, and I can't say I've ever felt I've missed out. Middleware is the right approach to that problem generally.

The point is to be able to have middleware that only runs on certain urls. For example, you might have middleware that only runs on a particular version of your API (`regexp: ^/1\/.*/`). I've used it fairly extensively.

The point being, now you're describing a completely different, less powerful framework. Which, yes, of course it's faster. You'll notice that's what Netflix ended up doing - they moved to `restify` from `express`.

You might as well just only allow routes to be strings and then you have the constant-time map implementation that the article describes as the expected implementation.

The match object will be of the form [undefined, ..., input_string, undefined, ...], so you can use something like m.indexOf(input_string) to find out the index. Unfortunately that's O(n) again, unless the engine uses a sparse array implementation...

You're right that it's O(n), but it's still faster than express js. It's not iterating through the array that's slow, its evaluating the members of that array. Express must check each route using JS functions that each execute a regexp match per route. Using a single regexp is much faster because 1.) by unioning the regexps you get the correct NFA, which will run much faster 2.) there's less function call overhead.

Iterating through the array looking for the first non-null value, then looking it up in a JS object O(1) matching capture group positions to routes is much faster than having to dispatch a bunch of functions. Additionally, it can be JITed to much faster code I would wager.

So, expressJS = N regexp matches, while this method = 1 regexp match + N null checks in the resulting array + 1 hashmap lookup in an object to return the proper route. The second solution is going to be much faster, even for large routing tables, esp. given how optimizable that array lookup code is.

You can get the index of the match via the .exec function. It returns an array. The first element is the match, and then an element for each capturing group. You'd need to keep track of how many sub-capturing groups each individual top-level capturing group has, but that's not terribly difficult.

As far as multiple matches, after you found a match, you would then test against a new regex that is everything to the right of the previous regex's captured group.

((a)|(b)|(c)|(d)) -> if b matches, you then test against ((c)|(d)), and so on.

This indicates it probably wont be much faster in JS

http://jsperf.com/regex-list-vs-full

Most of the time in the single-regex case is likely spent on allocating the matches array (which for a router with 300 routes would have over 300 undefined elements on every execution)

V8 is not quite the typical dynamic language runtime. Code that would be dead slow in others is optimized really well by the amazing JIT.

Interesting, I'm looking at it right now, and it's saying that the multiple regexes are ~ 50% slower in both chrome and firefox. Am I missing something? It looks like the single regex actually is a significant win.

It is interesting how much allocation changes things though, very cool that you made this.

Yeah multiple regexes are slower, but the performance gain isn't too gigantic. If we had `regex.execIterable(string)` we could avoid allocating massive arrays and maybe get a really significant difference

Regexps with backtracks are not regular languages (IIRC, right?), does that matter here?

That's right. Typical routing regexes will not use backreferences, so that's not really an issue here. However, most routes do have parameters implemented as capture groups (which, I believe, is also not technically a feature of regular expressions). One simple solution would be to use a big regex (the union of all the routes) to determine which route it is (in O(n) time), and then once you know the route, use another regex to parse the parameters in the URL. So each route lookup requires 2 regex matches rather than N.

Just re-read this and realized it's unclear: when I said O(n) time, I meant linear in the length of the URL to be parsed. The point is that with this technique, it doesn't matter how many routes there are.

Given that combined regex, how do you determine which of the routes that went in to it was the one that matched?

If it matched the first, match[2] is set. If it matched the second, match[3] is set.

Or you use a better regexp library than the default JS one and use named captures.

It looks like routes are either strings (exact match) or regular expression objects. I don't think there's a way to combine regular expressions in JavaScript.

I don't think this was an unreasonable implementation. Sure, it could be optimized, but no-one needed it enough to do the work. (Even Netflix didn't need a faster matcher, they needed a matcher that didn't slow down between the 1st match and the nth.)

What I'm saying is that the pipe (or) "|" is a cheap way to combine regexps. It has its limitations, but its better than an O(n) search through an array. The regexp parser can create an NFA that is far more optimized.

In JS, "far more" isn't quite that dramatically far as in other dynamic language runtimes. See http://jsperf.com/regex-list-vs-full

Oh yes, I forgot about the legendary Ruby On Rails code quality: http://puppetlabs.com/security/cve/cve-2013-0277