BUG: param with same prefix to static route not working as expected

[daymade]

code version:

last commit index: 23d011e

Current behavior:

when we pass a param to a params route, and the param has same prefix to a static route,
we got two wrong results:
not found and handler right, extracted params wrong

Expected behavior:

1. route me to right handler
2. extract params correct

Steps to reproduce:

1. add one route /:id
2. add another route /users
3. add third route /usersnew
4. in postman we visit an url /usersnew1
5. handler not found

Related code:

paste this two tests to router_test.go

func TestIssue61_1(t *testing.T) {
	r := NewRouter()

	// Routes
	r.Add("GET", "/:id", func(w http.ResponseWriter, r *http.Request) {
		w.Write([]byte("param_" + Param(r, "id")))
	})
	r.Add("GET", "/users", func(w http.ResponseWriter, r *http.Request) {
		w.Write([]byte("static_users"))
	})
	r.Add("GET", "/usersnew", func(w http.ResponseWriter, r *http.Request) {
		w.Write([]byte("static_usersnew"))
	})

	// Route > /users
	req, _ := http.NewRequest("GET", "/users", nil)
	h := r.Find(req)
	w := httptest.NewRecorder()
	if assert.NotNil(t, h) {
		h(w, req)
		assert.Equal(t, "static_users", w.Body.String())
	}

	// Route > /usersnew
	req, _ = http.NewRequest("GET", "/usersnew", nil)
	h = r.Find(req)
	w = httptest.NewRecorder()
	if assert.NotNil(t, h) {
		h(w, req)
		assert.Equal(t, "static_usersnew", w.Body.String())
	}

	// Route > /:id
	req, _ = http.NewRequest("GET", "/123", nil)
	w = httptest.NewRecorder()
	h = r.Find(req)
	if assert.NotNil(t, h) {
		h(w, req)
		assert.Equal(t, "123", Param(req, "id"))
		assert.Equal(t, "param_123", w.Body.String())
	}

	// Route > /:id
	req, _ = http.NewRequest("GET", "/users123", nil)
	w = httptest.NewRecorder()
	h = r.Find(req)
	if assert.NotNil(t, h) {
		h(w, req)
		assert.Equal(t, "users123", Param(req, "id"))
		assert.Equal(t, "param_users123", w.Body.String())
	}

	// Route > /:id
	// BAD CASE 1 HERE
	req, _ = http.NewRequest("GET", "/usersnew1", nil)
	h = r.Find(req)
	w = httptest.NewRecorder()
	if assert.NotNil(t, h) {
		h(w, req)
		//expected: "usersnew1" received: ""
		assert.Equal(t, "usersnew1", Param(req, "id"))
		//expected: "param_usersnew1" received: "Not Found"
		assert.Equal(t, "param_usersnew1", w.Body.String())
	}
}

func TestIssue61_2(t *testing.T) {
	r := NewRouter()

	// Routes
	r.Add("GET", "/users", func(w http.ResponseWriter, r *http.Request) {
		w.Write([]byte("static_users"))
	})
	r.Add("GET", "/usersnew", func(w http.ResponseWriter, r *http.Request) {
		w.Write([]byte("static_usersnew"))
	})
	// NOTE HERE
	// we add param route after added two static routes
	r.Add("GET", "/:id", func(w http.ResponseWriter, r *http.Request) {
		w.Write([]byte("param_" + Param(r, "id")))
	})

	// Route > /users
	// Works well
	req, _ := http.NewRequest("GET", "/users", nil)
	h := r.Find(req)
	w := httptest.NewRecorder()
	if assert.NotNil(t, h) {
		h(w, req)
		assert.Equal(t, "static_users", w.Body.String())
	}

	// Route > /:id
	// Works well
	req, _ = http.NewRequest("GET", "/123", nil)
	h = r.Find(req)
	w = httptest.NewRecorder()
	if assert.NotNil(t, h) {
		h(w, req)
		assert.Equal(t, "123", Param(req, "id"))
		assert.Equal(t, "param_123", w.Body.String())
	}
	// Works well
	req, _ = http.NewRequest("GET", "/users123", nil)
	h = r.Find(req)
	w = httptest.NewRecorder()
	if assert.NotNil(t, h) {
		h(w, req)
		assert.Equal(t, "users123", Param(req, "id"))
		assert.Equal(t, "param_users123", w.Body.String())
	}

	// Route > /:id
	// BAD CASE HERE
	// NOTE this case and the above one(issue61_1) seem to be identical,
	// But there are one difference, we add param route after added two static routes
	// Which gives us different result: the matched handler is right, but params extracted is wrong
	req, _ = http.NewRequest("GET", "/usersnew1", nil)
	h = r.Find(req)
	w = httptest.NewRecorder()
	if assert.NotNil(t, h) {
		h(w, req)
		//expected: "usersnew1" received: "new1"
		assert.Equal(t, "usersnew1", Param(req, "id"))
		//expected: "param_usersnew1" received: "param_new1"
		assert.Equal(t, "param_usersnew1", w.Body.String())
	}
}

[baylee]

Encountered the same issue, got Not Found if a parameter in a parameterized route had even the same initial character as a non-parameterized route. Having different methods did not change the result.

Example:

router.Post("/foo/apple", foo.AppleHandler)
router.Get("/foo/:ID", foo.IDHandler)

When I GET /foo/abcde, I get "Not Found". Expectation is that I would be routed to foo.IDHandler.

[husobee]

Will look into this today. Thanks for the report.

[husobee]

@baylee: I am not seeing this problem based on your example, here is how i tried to reproduce:

package main

import (
        "log"
        "net/http"

        "github.com/husobee/vestigo"
)

func main() {
        // setup router and example route
        routes := vestigo.NewRouter()

        routes.Post("/foo/apple", PostExampleHandler)
        routes.Get("/foo/:ID", GetExampleHandler)

        log.Fatal(http.ListenAndServe(":1234", routes))
}

// GetExampleHandler - the "latest" handler function for /example
func GetExampleHandler(w http.ResponseWriter, r *http.Request) {
        w.WriteHeader(200)
        w.Write([]byte("example latest get foo id"))
}

// PostExampleHandler - the "latest" handler function for /example
func PostExampleHandler(w http.ResponseWriter, r *http.Request) {
        w.WriteHeader(200)
        w.Write([]byte("example latest post foo apple"))
}

With these results:

$ curl -XPOST http://localhost:1234/foo/apple -D -; echo
HTTP/1.1 200 OK
Date: Tue, 02 May 2017 15:17:07 GMT
Content-Length: 29
Content-Type: text/plain; charset=utf-8

example latest post foo apple


$ curl http://localhost:1234/foo/abcde -D -; echo                           
HTTP/1.1 200 OK
Date: Tue, 02 May 2017 15:15:20 GMT
Content-Length: 25
Content-Type: text/plain; charset=utf-8

example latest get foo id

It seems the problem that @tsongknows is finding is due to the path going deeper in the radix tree without a / seperator. Below is a visualization

/     
      -> :id
      -> users
               -> new

That being the case, currently the logic is, if there is not an exact match, the router will "back up" to the parent node's children, and see if there is parameter-ized or wildcard match on that level.

Since in our failure example, we are trying to use /usersnew1 the router goes down users path and then new path, and can't go any further, therefore backs up to the users path and looks for a parameter-ized or wildcard match, and can't find one. I feel the correct logic should be, go back as far as possible up until the preceding /looking for parameter-ized or wildcard matching.

I feel like I can get some cycles tonight to figure out a solution for this issue. Will keep you posted.

[husobee]

@tsongknows @baylee: potential fix in branch issue-61. I have included the unit tests that are in this issue, and they now pass. Also included unit tests for testing wildcards across trie edge bounds as well. Tests for Issue61_2 were finding an unrelated bug also corrected in the PR, which was on insertion, on node split the child nodes were not updated with the reference to the new parent node. Thank you so much for finding this issue. If you don't mind testing this fix for me, I would appreciate it!

[daymade]

hi @husobee , thank you for your quick response!
I just test the new code in #63, all of the tests are passed, but I was wondering why do you commented out TestRouterMultiRoute on line 374 in router_test.go, if it is useless or a temporary hot fix?
see d97bab7#commitcomment-21992935

[husobee]

Right, still looking into that failure. I think I know why that is not working right. Hope to have a fix soon.

…

On May 2, 2017 10:33:47 PM EDT, tiansheng ***@***.***> wrote: hi @husobee , thank you for your quick response! I just test the new code in #63, all of the tests are passed, but I was wondering why do you commented out `TestRouterMultiRoute` on `line 374` in `router_test.go`, if it is useless or a temporary hot fix? see d97bab7#commitcomment-21992935 -- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: #61 (comment)

[daymade]

hi @husobee, nice job you have done!

luckless i have some tests still been failed 😅, about prefix returning from r.find

...
func (r *Router) add(method, path string, h http.HandlerFunc, cors *CorsAccessControl) {
...
func (r *Router) find(req *http.Request) (prefix string, h http.HandlerFunc) {

Could you tell me if the prefix returned and the route path we added should be identical?

If they need to be equal , please see following unit test:

// we can put this test in route_test.go 
func TestRouter_Match_StaticAndParamWithSamePrefix(t *testing.T) {
	type args struct {
		req *http.Request
	}

	wantParamTemplate := "/order/:id/address/:no"
	staticTemplate := "/order/new/address"

	r := NewRouter()

	r.Add("POST", wantParamTemplate, func(w http.ResponseWriter, r *http.Request) {
		w.Write([]byte(wantParamTemplate))
	})
	r.Add("POST", staticTemplate, func(w http.ResponseWriter, r *http.Request) {
		w.Write([]byte(staticTemplate))
	})

	// OK
	normalRequest, _ := http.NewRequest("POST", "/order/someid/address/123", nil)

	prefix1, h1 := r.find(normalRequest)

	w1 := httptest.NewRecorder()
	if assert.NotNil(t, h1) {
		h1(w1, normalRequest)

		assert.Equal(t, wantParamTemplate, w1.Body.String())

		assert.Equal(t, wantParamTemplate, prefix1)
	}

	// BAD CASE?
	// NOTE: label of segment ns is 'n'
	StaticAndParamWithSameLabelRequest, _ := http.NewRequest("POST", "/order/ns/address/123", nil)

	prefix2, h2 := r.find(StaticAndParamWithSameLabelRequest)

	w2 := httptest.NewRecorder()
	if assert.NotNil(t, h2) {
		h2(w2, normalRequest)

		// Matched right handler
		assert.Equal(t, wantParamTemplate, w2.Body.String())

		// BAD CASE?
		// expected: "/order/:id/address/:no" received: "/order/new/address:/address/:id"
		assert.Equal(t, wantParamTemplate, prefix2)
	}
}

// perhaps node.findChild need to be reviewed

[husobee]

Will look into this tonight. It is pretty strange it is finding the correct handler, and not returning the correct prefix in this instance. Thanks!

[husobee]

@tsongknows I updated the PR with another fix to solve that issue you were seeing, and also removed some dead code paths. Please let me know how that works for you. All tests are passing now.

[daymade]

@husobee it works.
before you merge it there are some variable names seems a little uncomfortable

func (n *node) findChild(l string, t ntype) *node

l here is not meaning for label, but for search
would you give some refactoring to it? that will increase the readability, in a sense

[husobee]

Great suggestion. Updated, and just pushed.

[daymade]

looks great! I would like to close this issue, thanks for all things you have done @husobee

[husobee]

Cool. Merged. Thanks for the bug report.