Route matching
jhvst opened this issue · 7 comments
Hi,
I have been testing your router lately and I have run into unexpected behaviour. I'm not completely sure whether it is a bug in radix tree implementation or design choice, but I'll give you an example below.
package main
import (
"log"
"net/http"
"github.com/husobee/vestigo"
)
func main () {
r := vestigo.NewRouter()
r.Get("/new", GetWelcomeHandler)
r.Get("/:name", GetWelcomeHandler)
log.Fatal(http.ListenAndServe(":1234", r))
}
func PostWelcomeHandler(w http.ResponseWriter, r *http.Request) {
name := vestigo.Param(r, "name") // url params live in the request
w.WriteHeader(200)
w.Write([]byte("welcome " + name +"!"))
}
func GetWelcomeHandler(w http.ResponseWriter, r *http.Request) {
w.WriteHeader(200)
w.Write([]byte("welcome!"))
}
Now I'm going to make some GET requests:
01:53:54 ~/Github/vestigo-example $ http http://localhost:1234/new
HTTP/1.1 200 OK
Content-Length: 8
Content-Type: text/plain; charset=utf-8
Date: Sat, 12 Dec 2015 19:41:14 GMT
welcome!
01:53:54 ~/Github/vestigo-example $
01:53:54 ~/Github/vestigo-example $ http http://localhost:1234/foobar
HTTP/1.1 200 OK
Content-Length: 8
Content-Type: text/plain; charset=utf-8
Date: Sat, 12 Dec 2015 19:42:19 GMT
welcome!
01:53:54 ~/Github/vestigo-example $
This is expected, but here's an edge case:
01:53:54 ~/Github/vestigo-example $ http http://localhost:1234/new-foobar
HTTP/1.1 404 Not Found
Content-Length: 9
Content-Type: text/plain; charset=utf-8
Date: Sat, 12 Dec 2015 19:43:15 GMT
Not Found
01:53:54 ~/Github/vestigo-example $
I'd expect the server to return welcome instead of 404. What happens here is that if you request anything which starts new you end up getting 404. Swapping route order in main.go does not affect anything.
I have little knowledge of radix tree implementations, so I thought to ask you first whether this is a design choice or is it something which could be fixed?
This is very tricky and unfortunately not very easily remedied. The routes for your example above end up looking like this in vestigo:
└── /, 0xc82005a0e0: type=0, parent=0x0, resource=&{0xc82005a380 <nil> <nil> <nil> <nil> <nil> <nil> <nil> 0x4b29d0 }
├── new, 0xc82005a2a0: type=0, parent=0xc82005a0e0, resource=&{0xc82005a230 <nil> <nil> 0x401520 <nil> <nil> <nil> <nil> <nil> GET, HEAD}
└── :, 0xc82005a4d0: type=1, parent=0xc82005a0e0, resource=&{0xc82005a460 <nil> <nil> 0x401350 <nil> <nil> <nil> <nil> 0x4b29d0 GET, HEAD}
The first "branch" in the prefix trie happens at / where your two routes have the same prefix in common. Then they break into new and wildcard branches. At this point, the next character set is matched, in your new-foobar example we match the prefix new and then check for children nodes that can match the remainder -foobar of which the new node has none, so we return a Not Found.
I would recommend reworking your url scheme to the below:
func main () {
r := vestigo.NewRouter()
r.Get("/new", GetWelcomeHandler)
r.Get("/new:suffix", GetWelcomeHandler)
r.Get("/:name", GetWelcomeHandler)
log.Fatal(http.ListenAndServe(":1234", r))
}
The above will give you what I think you want, where you have a default "catch-all" route, and one that matches exactly "new" and handles it differently. I hope this is helpful.
I will try to work a branch of vestigo tomorrow to see if I can't make it do what you are asking without affecting usability and performance. I feel like the only way to make this happen is to always check the current node's parent for child nodes that have a wildcard designation if there is a miss. Will update this issue tomorrow with progress.
Great! Thank you for taking the time to explain and suggest a solution to my problem!
I also appreciate your willingness to look into covering my case. However, I think that fixing the url scheme is easier than bending the algorithm to be aware of edge-cases such in my example.
To elaborate, I have URL scheme like this:
r.Get("/post/new", protectedHandler.ThenFunc(func(w http.ResponseWriter, r *http.Request) {
render.R.HTML(w, 200, "post/new", nil)
}).(http.HandlerFunc))
r.Post("/post/search", postSearch.ThenFunc(SearchPost).(http.HandlerFunc))
r.Get("/post/:slug/edit", protectedHandler.ThenFunc(EditPost).(http.HandlerFunc))
r.Post("/post/:slug/edit", postForm.ThenFunc(UpdatePost).(http.HandlerFunc))
r.Get("/post/:slug/delete", protectedHandler.ThenFunc(DeletePost).(http.HandlerFunc))
r.Get("/post/:slug/publish", protectedHandler.ThenFunc(PublishPost).(http.HandlerFunc))
r.Get("/post/:slug/unpublish", protectedHandler.ThenFunc(UnpublishPost).(http.HandlerFunc))
r.Get("/post/:slug", ReadPost)
r.Post("/post/new", postForm.ThenFunc(CreatePost).(http.HandlerFunc))
The routing is pretty dirty, but worked with martini. When I migrated the code to vestigo my tests showed that posts which slugs started with s or n returned 404. I eventually figured out that it was because I have two cases for search and new. I have exceptions for those in my backend logic, but I guess it would be easier to just change the routes to /posts/search and /posts/new. Then I would not need the exceptions or the additional routes which you gave an example of.
I can wait a day to give you the time to look into the issue, but as I thought, the easier solution would be to just rewrite my url scheme.
Ah, I completely see what you mean. I will look into this more tomorrow to see if I can solve this edge case. Will be in touch with findings. Thank you!
On December 12, 2015 6:17:26 PM EST, Juuso Haavisto notifications@github.com wrote:
Great! Thank you for taking the time to explain and suggest a solution
to my problem!I also appreciate your willingness to look into covering my case.
However, I think that fixing the url scheme is easier than bending the
algorithm to be aware of edge-cases such in my example.To elaborate, I have URL scheme like this:
r.Get("/post/new", protectedHandler.ThenFunc(func(w http.ResponseWriter, r *http.Request) { render.R.HTML(w, 200, "post/new", nil) }).(http.HandlerFunc)) r.Post("/post/search", postSearch.ThenFunc(SearchPost).(http.HandlerFunc)) r.Get("/post/:slug/edit", protectedHandler.ThenFunc(EditPost).(http.HandlerFunc)) r.Post("/post/:slug/edit", postForm.ThenFunc(UpdatePost).(http.HandlerFunc)) r.Get("/post/:slug/delete", protectedHandler.ThenFunc(DeletePost).(http.HandlerFunc)) r.Get("/post/:slug/publish", protectedHandler.ThenFunc(PublishPost).(http.HandlerFunc)) r.Get("/post/:slug/unpublish", protectedHandler.ThenFunc(UnpublishPost).(http.HandlerFunc)) r.Get("/post/:slug", ReadPost) r.Post("/post/new", postForm.ThenFunc(CreatePost).(http.HandlerFunc))The routing is pretty dirty, but worked with martini. When I migrated
the code to vestigo my tests showed that posts which slugs started with
sornreturned 404. I eventually figured out that it was because I
have two cases forsearchandnew. I have exceptions for those in
my backend logic, but I guess it would be easier to just change the
routes to /posts/search and /posts/new. Then I would not need the
exceptions or the additional routes which you gave an example of.I can wait a day to give you the time to look into the issue, but as I
thought, the easier solution would be to just rewrite my url scheme.
Reply to this email directly or view it on GitHub:
#8 (comment)
@9uuso: I think I have a working solution to your problem. Please check out [this branch][https://github.com/husobee/vestigo/tree/check-sib] and give it a try. It passes all of the tests, including one I have added for your particular problem. If this works out, I will PR and merge to mainline. Thanks again!
My tests won't pass. I'll look into it and let you know if I'm able to figure out what gives. In isolated system the routes seem to work.
It might take a week or so, but I'll keep you updated!
Thanks, will stand by.
Did not get this figured out, I'll close the issue for now. Will reply if I get it solved.