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.