5 ms·

> 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.

> 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.

andrewvc 12y ago
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 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.
- thedufer 12y ago
  > 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.
  - deleted 12y ago
    [deleted]
  - andrewvc 12y ago
    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.
    - breuleux 12y ago
      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.
      - andrewvc 12y ago
        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.
        thedufer 12y ago
        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.
    - thedufer 12y ago
      > 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.
      - boblauer 12y ago
blinks 12y ago
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.
- rudolf0 12y ago
  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/ 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.
breuleux 12y ago
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...
- andrewvc 12y ago
  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.
FrozenCow 12y ago
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.
boblauer 12y ago
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.

andrewvc 12y ago

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 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.

thedufer 12y ago
> 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.
- deleted 12y ago
  [deleted]
- andrewvc 12y ago
  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.
  - breuleux 12y ago
    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.
    - andrewvc 12y ago
      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.
      - thedufer 12y ago
        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.
  - thedufer 12y ago
    > 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.
    - boblauer 12y ago

blinks 12y ago

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.

rudolf0 12y ago
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/ 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.

breuleux 12y ago

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...

andrewvc 12y ago
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.

FrozenCow 12y ago

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.

boblauer 12y ago

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.