Wildcard lookup issue with previously defined deep paths...

[crisward]

With the following Kemal app, if I go to /reviews/ I get page not found.

require "kemal"

get "/*" do |env|
  "reviews"
end

get "/resources/js/*" do |env|
  "some js"
end

get "/robots.txt" do |env|
  "robots"
end

Kemal.run

However if I remove either of the two routes begining with "r" the wildcard matches and I get back reviews, eg this works

require "kemal"

get "/*" do |env|
  "reviews"
end

get "/robots.txt" do |env|
  "robots"
end

Kemal.run

I'm reporting this here as this looks like a radix issue, @sdogruyol what do you think?

[luislavena]

Will be possible for you to provide information about the version of Radix being used? I've made some fixes for globing in the latest version that might help.

Right now a bit busy with work but will try to reduce the example to a Radix one over the weekend, even better if you can (look at past closed PR for examples)

Thank you.

[sdogruyol]

I just tried with Kemal 0.19.0 / Radix 0.3.8 and can confirm it.

[crisward]

Yep, we're using the latest too.

[crisward]

This returns "not found"

require "radix"

tree = Radix::Tree(Symbol).new
tree.add "/get/*", :one
tree.add "/get/robots.txt", :two
tree.add "/get/resources/js/*", :three

result = tree.find "/reviews/"

if result.found?
  puts result.payload
else
  puts "not found"
end

This works, and returns "one"

require "radix"

tree = Radix::Tree(Symbol).new
tree.add "/get/*", :one
tree.add "/get/robots.txt", :two

result = tree.find "/reviews/"

if result.found?
  puts result.payload
else
  puts "not found"
end

This also works, and returns "one"

require "radix"

tree = Radix::Tree(Symbol).new
tree.add "/get/*", :one
tree.add "/get/resources/js/*", :three

result = tree.find "/reviews/"

if result.found?
  puts result.payload
else
  puts "not found"
end

[luislavena]

Thank you @crisward for the reduction.

I think the issue might be that some nodes already start with r and globing is lower in the hierarchy than these two, which might result in not found when performing the look up.

Globing is a tricky part that definitely needs a bit more of testing, so thank you for the real-life use cases!

Will spend some time this weekend working on this and will update.

Cheers.

[crisward]

Not a problem. Thanks again for a excellent library.

[luislavena]

Hello folks,

Wanted to give an update on this since work$ was a priority over the past week and kept me away from providing details.

This has resulted a bit more complicated than originally planned. As right now, the walking and checking nodes inside the Tree is done by the tree itself, but this issue expose a problem with that approach.

To better describe it, let's draw how nodes are organized after the add is done:

tree = Radix::Tree(Symbol).new
tree.add "/*", :one
tree.add "/robots.txt", :two
tree.add "/resources/js/*", :three

And here is the output:

# ( 1) /
# ( 1)  r
# ( 9)   obots.txt
# (12)   esources/js/*
# ( 0)  *

Problem is, /reviews/ starts with r, tree walks down the nodes nodes, it matches / to the root one, then moves into r and compare against the children nodes, at which points determines is not found and returns.

At that point, is too late to roll back to parent node (root in this case) and continue comparing against the others.

Gave this a bit more of thought and I think the solution for this will be move the node matching aspect to the node itself, which might simplify the code of #find method but at the same time, allow checking against multiple children.

A technical note come to my attention on this prior jumping into the code: need to be careful not to share state of the walk process of the nodes (ie. not using an instance variable for character reader) which might break when parallelism is added to the language.

---

I'm sorry to get back to you without a solution at this time, as this might require a bit more of work to properly handle it.

As a temporary workaround, I might suggest mapping some of the resources in a separate routing tree and arrange it in the middleware stack so the check happens before the globing one.

Not sure how Kemal uses Radix, but some pseudo code:

class App1 < Router
  get "/robots.txt", # ...
  get "/resources/js/*", # ...
end

class App2 < Router
  get "/*", # ...
end

stack = [App1.new, App2.new] of HTTP::Handler
HTTP::Server.new(..., stack)

(or something like that, again, apologizes for the lack of understanding on how Kemal can mount multiple applications).

Will try to work on a proper solution to this issue in July, as expect more available time for OSS.

Thank you for your patience.

Cheers.

[samueleaton]

Here is another problem with wildcards:

tree = Radix::Tree(String).new
node = "/yee/*/boi"

tree.add node, node
result = tree.find "/yee"
result.found? # => true, but should be false

Radix is saying that "/yee" matches "/yee/*/boi"

If this is unrelated I can make an issue.

[luislavena]

Hello @samueleaton,

Thank you for your comment, however that is the way globing was designed.

The usage of * makes anything after that to either be discarded or to be captured as a single thing:

require "./src/radix"

tree = Radix::Tree(Symbol).new
tree.add "/one/*/extra", :any

result = tree.find "/one"
pp result.found? # => true
pp result.params # => {"/extra" => ""}

result = tree.find "/one/foo/extra"
pp result.found? # => true
pp result.params # => {"/extra" => "foo/extra"}

Anything after * is the name to be given to the capture, so */extra makes /extra the name of the captured parameter and the value captured (first example is empty, second contains whatever was after /one/)

You will find more details in the specs:

https://github.com/luislavena/radix/blob/master/spec/radix/tree_spec.cr#L397-L475

If you want the route only matches when one and extra are present, you can use named parameter instead:

require "./src/radix"

tree = Radix::Tree(Symbol).new
tree.add "/one/:any/extra", :any

result = tree.find "/one"
pp result.found? # => false
pp result.params # => {}

result = tree.find "/one/foo/extra"
pp result.found? # => true
pp result.params # => {"any" => "foo"}

This definitely needs more documentation in the README and Radix::Tree, since lot of people are having confusion with * as wildcard instead of glob catcher.

Hope that helps.

Cheers.

[luislavena]

Hello @crisward, thanks for your patience.

I've pushed a fix for this in #30 and will be part of the next release.

Cheers.