You can use Ragel[1] to build your automaton.
Nice idea.
Edit: I did consider rewriting the runtime as a forth style interpreter as well but the time never appeared.
The function it performed to rebuild the DFA was to create an NFA for the new pattern stream (it worked on char *) and then walk both the existing master NFA and the merge them. Then it was converted from NFA to DFA via dragon book copy and paste algorithm (my discrete math isn't great). Both NFA and DFA were represented as a bunch of C structs tied together by pointers. Then a table generator walked the new DFA and generated a new state table. It was very naive but covered the common case where large parts of the byte stream to be matched were similar.
I've got MacVim up and writing it again. May post it as a Show HN if I get the time to finish it.
Your worst case is O(nd + O(constructing the new route's DFA)), where "n" is the number of nodes in the previous DFA and "d" is the number of nodes in the DFA of the new route.
Note that constructing r's DFA can be done beforehand, and hence the actual time the router will be offline is only O(nd).
(Assuming a simple 2 DFA -> 1 NFA -> DFA merge. Your worst case is that every possible pair from the two, and singleton of the two is present in the final DFA, i.e. ({node from old, node from new} -> nd + {node from old} -> n + {node from new} -> d) -> O(nd + n + d) -> O(n*d). Note that this isn't the classic O(2^n) behavior, because we know that, due to the old DFA and new route DFA being DFAs, only one node in n and one node in d can be present at a time in the final stateset.
A better bet may be to use the classic "lazily-constructed DFA" approach. In other words, keep it as an NFA while only converting (sets of) nodes to DFA nodes when necessary. If you are worried about memory, you can even do this only for "hot" sections of the NFA, or only for those sections of the NFA that have the most performance gain for the number of nodes added.
Sure, you could use all routes that match, but is there a way to specify the order for all handlers, and whether or not you should continue after one handler is done?
Sure you can. When you build your NFA, each accepting state is tagged with the route to which it corresponds. Converting to a DFA will merge states. Any accepting state in the DFA tagged with more than one route indicates a possible ambiguity. How you handle that ambiguity is up to you.
One strategy is to just fail at route-building time. Another is to order the routes by priority (which priorities maybe coming from order in the source code) and eliminate from each accepting state all routes except the one with the highest priority.
The latter approach gives you the "defined order" semantics you want.
Unless you go the NFA route, but I'm pretty sure that costs non-constant space.
So, in terms of the GP's post, yes, this is an O(1) (with respect to number of routes) solution.
I suspect this is a slight overestimate, but the point stands - non-trivial apps could quickly build very large state graphs.
Other than that, if you are concerned about automaton size you can use a non-deterministc automaton instead of a deterministic one. You spend a bit more time (at each iteration you have to update a list of "active" states, while in the DFA case there is always a single active state) but on the other hand the automaton itself is much more compact.
That's not very large, since you can store a DFA very compactly in a table (C array with structs). The table stores the transitions, which only have the character and the target state. Then you either keep an array with state offsets in the transition table, or you modify transition tables such that each transition points at the first transition of the target state.
If I have the routes /foo/bar and /foo/bar/(\d+) I can generate the regexp ((^\/foo\/bar$)|(^\/foo\/bar\/\d+$))
I'm not at all surprised, the quality of software in node is pretty low, I've seen numerous issues in node libs being just as boneheaded. I swear, the fact that the express devs overlooked a key optimization is crazy. Rails, by way of example, uses the Journey engine to solve this problem (https://github.com/rails/journey)
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.
>>> 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'}
Nice to know that what I made is considered the best solution algorithmically.
> /(^\/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' ]
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.
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.
"/foo/bar/3".match(/((^\/foo\/bar\/.*)|(^\/foo\/bar\/(\d+)$)|(^\/baz))/) =>
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.
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 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.
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.
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.
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.
It is interesting how much allocation changes things though, very cool that you made this.
Or you use a better regexp library than the default JS one and use named captures.
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.)
That way, if you have any route definitions that match early on, especially if they allow execution to continue ( by calling next() ), they will run before any following code does.
This allows your code to be very expressive and intuitive when reading it, as things have a defined order.
I imagine the recursion is also done so that you can use a route object anywhere in that ordered stack and it will apply all its own handlers, in the order they were defined in the code.
Its actually quite clear - most routes are defined by a regex rather than a string, so there is no built-in structure (if there's a way at all) to do O(1) lookups in the routing table. A router that only allowed string route definitions would be faster but far less useful.
I can't explain away the recursion, though. That seems wholly unnecessary.
Edit: Actually, I figured that out, too. You can put middleware in a router so it only runs on certain URL patterns. The only difference between a normal route handler and a middleware function is that a middleware function uses the third argument (an optional callback) and calls it when done to allow the route matcher to continue through the routes array. This can be asynchronous (thus the callback), so the router has to recurse through the routes array instead of looping.