Padrino's router design - i.e., retiring http_router

dariocravero commented 11 years ago

Hey everyone,

As we all know, towards new versions we need to rework our router.

A part of it is to remove http_router since it's not actively maintained anymore and our efforts to make it work in Padrino are quite patchy :S.

I'm opening this issue so we can all discuss what we think this new router's DSL should look like, which options we want to support, which ones we'll drop, etc.

I reckon this will provide more clarity and help us draft a spec to implement it with a roadmap in mind :)

@padrino/core-members, thoughts?

Ortuna commented 11 years ago

perhaps Mustermann can be looked to for DSL inspiration.

skade commented 11 years ago

Mustermann is really cool and I would adopt it directly - if it wasn't for the Ruby 2.0 requirement. (A word of warning: Sinatra 2.0 will require it, too).

As I attempted this a few month ago, I'll give a short overview:

We're a bit stuck between a rock and a hard place. I would prefer not to write our own router. Yet, all of our options are bad:

we want to move away from http_router due to its problematic recompiling behaviour
journey was promising, but was included in Rails core again, which makes it unusable. Still, adopting the concept is an option.
Mustermann is a cool base library to build a router quickly, but is strictly 2.0
There are no other mature routing libraries in ruby land that I know of

These are my biggest painpoints that make having our own router somehow a reasonable option :/.

On Jul 8, 2013, at 6:39 PM, Sumeet Singh notifications@github.com wrote:

perhaps Mustermann can be looked to for DSL inspiration.

— Reply to this email directly or view it on GitHub.

dariocravero commented 11 years ago

Would it be very hard to add a 1.9.x compatibility layer to Mustermann?

Ortuna commented 11 years ago

@dariocravero I see a lot of Ruby 2.0 keyword arguments.

@skade it also looks like Mustermann was created mainly for Sinatra 2.0 as it seems.

Ortuna commented 11 years ago

Looks like someone is asking about it here

gcapizzi commented 11 years ago

Having a well written and actively maintained Rack router would be a huge win for the whole Ruby community. Every framework (Rails, Sinatra, Cuba) has basically reinvented the wheel with non-reusable solutions. So, if you plan to write a new router from scratch, I'd be glad to help.

nesquena commented 11 years ago

I'd agree as well although I believe @rkh has developed the beginnings of an extensible while working on Sinatra 2. Would be cool to have a robust rack http router though akin to what http_router was trying to do.

rkh commented 11 years ago

I was thinking of either adding a minimal router to Mustermann or releasing one separately. Though that was just a quick idea, as I've only used it with Sinatra so far.

gcapizzi commented 11 years ago

Here is an extremely naive implementation I've started some time ago: https://github.com/gcapizzi/roadie

namusyaka commented 11 years ago

I made a plugin for routing of padrino which is using mustermann. https://github.com/namusyaka/howl-router

dariocravero commented 11 years ago

Looks promising at a first glance @namusyaka :) Can't wait to test it... Thanks for taking the time for getting something going :)

namusyaka commented 11 years ago

I hope this will be of some help. Thanks.

nesquena commented 11 years ago

Yeah nice work @namusyaka! Excited about the potential in Padrino 0.12.0 if we can plug in a new router, and lock to AS4 and Ruby 1.9.2.

—

Nathan Esquenazi CodePath Co-founder http://thecodepath.com

On Thu, Aug 22, 2013 at 12:31 PM, namusyaka notifications@github.com wrote:

Thanks. I hope this will be of some help.

Reply to this email directly or view it on GitHub: https://github.com/padrino/padrino-framework/issues/1339#issuecomment-23116412

nesquena commented 11 years ago

How far away do you think we would be from being able to rip http-router out and replace it with howl for 0.12.0? If there was one thing I'd hope we can get done before 0.12.0, it would probably be using a new router. /cc @namusyaka @DAddYE @dariocravero

nesquena commented 11 years ago

Before we go 1.0 (and in conjunction with a new router), let's do some serious spring cleaning on the router itself. Do you guys all still like the ideas proposed here: https://github.com/padrino/padrino-framework/issues/747? /cc @padrino/core-members

namusyaka commented 11 years ago

It's easy for us to replace with howl-router. I want to hear everyone's opinion. BTW, howl-router is passing tests of padrino-framework with the exception of a few tests. I'll fix a few bugs for failed tests in a few days.

DAddYE commented 11 years ago

Hi,

I like a lot your router, I would like to drop, finally, http-router and thus switch to yours BUT only if you would like to merge you library directly into padrino-core. I don’t want to do the same mistake to relay on an external library :(

What do you think?

namusyaka commented 11 years ago

Yes, you are right, Sir. I think so, too. I'd like to merge a redesigned howl-router into padrino-core.

nesquena commented 11 years ago

Yeah I think that makes sense. Something as core to our functioning as the router itself needs to be kept internally to ensure its constantly maintained. Will be awesome to see how much it can hopefully clean up the routing code.

—

Nathan Esquenazi CodePath Co-founder http://thecodepath.com

On Sat, Sep 7, 2013 at 1:19 AM, namusyaka notifications@github.com wrote:

Yes, you are right, Sir. I think so, too.

I'd like to merge a redesigned howl-router into padrino-core.

Reply to this email directly or view it on GitHub: https://github.com/padrino/padrino-framework/issues/1339#issuecomment-23985050

skade commented 11 years ago

I've got two questions about howl:

can we also use it for the mounter?
does it support Cascade-Style routing like journey does?

This means, can we - in theory and practice - support the mounting of other frameworks like grape in the future?

rkh commented 11 years ago

can we also use it for the mounter?

I was considering adding a feature to mustermann that allows you to easily match the beginning of a string and will also give you the remainder, to make the whole SCRIPT_NAME/PATH_INFO dance easier.

namusyaka commented 11 years ago

@rkh Thank you so much!

@skade Sorry, I didn't consider the Cascade-style... But I want to support it.

namusyaka commented 11 years ago

Hi. I tried to merge the redesigned router (but the new router doesn't support mounter) into padrino-core. We need to rewrite test_restful_routing.rb, but some tests that have been skipped will pass.

here

ahacking commented 11 years ago

Not to take away from any of the good work here but I would like to see the router support class based controllers (and inheritance) as discussed in #747 I'm not fond of everything being lumped in together. I have rails projects that make quite a lot of use of both controller and view inheritance to keep things very DRY. It would be good to be able to leverage the OO features of ruby and keep methods related to a particular controller isolated to that controller and it's descendants and use protected methods.

graudeejs commented 11 years ago

@ahacking, I wanted to write exactly the same.

nesquena commented 11 years ago

@namusyaka Nice work so far, do you want to create a branch on this repo for replacing the router? Seems like it's possible we could swap out http_router for the next big release.

@ahacking @graudeejs Like this right, I think this was actually created out of a similar frustration? http://scorchedrb.com/

namusyaka commented 11 years ago

@nesquena Thanks. Should I create a branch on this repo? I was going to send pull request from my forked repo.

nesquena commented 11 years ago

Yeah in this case, maybe you can push the branch on this repo so we can all play around with it too since it's a pretty major change.

namusyaka commented 11 years ago

I understand. I'll create a branch before the end of the day. Thanks for advice!

namusyaka commented 11 years ago

I'm done. here

nesquena commented 11 years ago

Great thanks!

ahacking commented 11 years ago

@nesquena yes something like scorchedrb !

Another aspect of routing that I was curious about was the "iterate over route patterns" vs a combined single regex. I haven't looked into what musterman does but it seemed possible that one could compile all of the route patterns into a single regex using say named grouped expressions so that one knows which route(s) matched. Based on the way the DFAs work in regex evaluation you would be able to route requests with a single match call similar to the way packet classifiers/sniffers work at wire speed with many thousands of patterns.

Ortuna commented 11 years ago

@ahacking Just last night I was watching http://www.youtube.com/watch?v=41PvAPSX0wg Jose explains the lookup of Sinatra and how it would go and match every route to see if it is a match. This would cause the request time to go up n times because the routes are above the one you are requesting.

rkh commented 11 years ago

A few remarks:

Mustermann is indeed able to combine multiple routes into one, as they are parsed into an AST that can be combined at will (this is used for the except feature, too), from which it then generates an efficient regexp and expand patterns.
Ruby does not use a parallel DFA for regexps, instead it uses (as is common) backtracking, which allows for advanced features like look-behind. So what you'd be actually saving is returning to Ruby land. While this is indeed faster, it is not a different complexity class compared to sequential matching.
If you have enough routes so that this matters, you are probably doing it wrong.
Rails moving from a sequential matching with rack-mount to a DFA with journey has not yielded significantly better routing performance (though solved other problems for them unrelated to that fact).

ahacking commented 11 years ago

@rkh Thanks for your detailed reply on Mustermann and Journey. Ive read a number of papers on regexp and optimising DFAs, I wonder how many people actually use PCRE back-references (as opposed to only using capture groups) in routes which is one of the key reasons that a backtracking algorithm is used and the resulting exponential complexity (both time and memory). There are other algorithms that avoid these problems but they can't support back references.

If there was a Rack routing middleware that handled the vast majority of use cases and avoided the problem features of PCRE expressions there would be an overall CPU, memory efficiency and latency benefit in matching requests to handlers for all ruby web frameworks. Regexp state can (and will happily) take a significant/unbounded amount of RAM. Wire speed packet analysers and intrusion detection software like Snort have had to deal with this very issue and avoid the PCRE features that require a backtracking algorithm to make recognition both deterministic and practical for the number of patterns they have to contend with. Said another way, doing it the default ruby/PCRE way doesn't work because of the RAM and time required to evaluate the expressions on arbitrary packets.

We also have to consider that using an exponential time and space algorithm that uses backtracking can also introduce a possible denial of service attack vector into ALL applications. Its not the first time this has been a problem either: https://www.ruby-forum.com/topic/70726 and the Ruby 1.9 DoS regex exploit http://1337day.com/exploit/6576

I'd like to feel that I have some level of protection from an external attacker trivially sending a request to my applications which will happily consume all memory and crash because of fundamental properties of the PCRE regexp algorithm. I also acknowledge that this is a full stack issue and could equally apply to the web server, reverse proxy and so on depending on their use of regexp patterns and engine but there is something we can do here to avoid the problem entirely by the choices me make now.

nesquena commented 11 years ago

Since, the howl router required ruby 2.0, we might want to consider pushing this to 0.13.0 (or 1.0). What do you all think? Should we just bite the bullet and require 2.0 now for 0.12.0 or wait until the next major release? I could go either way? @padrino/core-members? Sinatra still supports 1.9.3 so that is one downside. I don't think 2.0 will be required until Sinatra 2.

namusyaka commented 11 years ago

I've tried to support for ruby1.9. https://github.com/namusyaka/mustermann/tree/19support

Test will pass except Mustermann::Shell test. However, I have a problem. I can't use Objectspace::Weakmap. (What should I use instead of it?)

skade commented 10 years ago

@namusyaka I know of multiple cross-platform replacement for WeakRef, but not for WeakMap (ref, weakling) :(.

rkh commented 10 years ago

I think the instance caching can simply be disabled conditionally based on WeakMap availability. As long as you instantiate the Mustermann routes only once it will just mean that the routes will get parsed twice (once from the part generating the internal regexp and once by the expander generating expansion patterns).

rkh commented 10 years ago

(I basically use it as an instance cache for immutable but expensive objects.)

namusyaka commented 10 years ago

@skade Really? I know of this library, too.

@rkh Let me make sure I understand you correctly. You mean it will down performance? And, I have question. Can you separate Mustermann's processing for 1.9 and 2.0? (e.g. Disable the instance caching if version is 1.9.)

rkh commented 10 years ago

@rkh Let me make sure I understand you correctly. You mean it will down performance?

It will increase "compile time" but does not have an impact on matching/expanding performance (except, possibly, for the first expansion).

Can you separate Mustermann's processing for 1.9 and 2.0? (e.g. Disable the instance caching if version is 1.9.)

That's what I was suggesting.

namusyaka commented 10 years ago

It will increase "compile time" but does not have an impact on matching/expanding performance (except, possibly, for the first expansion).

I got it. Thanks.

That's what I was suggesting.

Sorry, I didn't understand correctly. Then, can I use for that my branch? If so, I'll send pull request.

DouglasAllen commented 10 years ago

Before you drop Ruby-1.9.1 support please have a look at this error. I know it's not kosher to have all my gems at root but this is debians way of saying foobar.

~/dm-migrations-1.2.0/examples/padrino-integration/fixtures/single-apps$ bundle exec ruby sinatra_routing.rb

/var/lib/gems/1.9.1/gems/padrino-core-0.12.4/lib/padrino-core/application/routing.rb:489:in 'route': undefined local variable or method 'protect_from_csrf' for SinatraRouting:Class (NameError) from /var/lib/gems/1.9.1/gems/padrino-core-0.12.4/lib/padrino-core/application/routing.rb:344:in 'get' from sinatra_routing.rb:23:in '<class:SinatraRouting>' from sinatra_routing.rb:19:in '<main>'

I don't know if this will help anybody but it's better than just complaining about it. An old saying: Too many chickens cooking in one pot makes a mess. (boil over) Takes a crue like team to clean it up. Beleive it or not? I don't have the money to hire this may people so please be careful. :dash:

dariocravero commented 10 years ago

@DouglasAllen could you provide us with a failing sample to try it out?

namusyaka commented 9 years ago

Closing in favour of #1800 @DouglasAllen Please open an issue if you still have the problem.

padrino / padrino-framework

Padrino's router design - i.e., retiring http_router #1339

Thanks. I hope this will be of some help.

I'd like to merge a redesigned howl-router into padrino-core.