Tried to place key X at same level as Y

[jwoertink]

I saw the caveat note on this, but after digging in to the code, I'm thinking this issue might be able to be fixed.

Doing this fails:

tree = Tree(Symbol).new
tree.add "/members/:id/edit", :member_edit
tree.add "/members/export", :members_export
tree.add "/members/:id/videos", :member_videos

but doing this works:

tree = Tree(Symbol).new
tree.add "/members/:id/edit", :member_edit
tree.add "/members/:id/videos", :member_videos
tree.add "/members/export", :members_export

Here's an example of how they differ:

[11:49AM] radix (bug/multipath_error)$ icr -r ./src/radix
 => ok
icr(0.19.4) > tree1 = Radix::Tree(Symbol).new
 => #<Radix::Tree(Symbol):0x104752f40 @root=#<Radix::Node(Symbol):0x104754d40 @payload=nil, @priority=0, @key="", @placeholder=true, @children=[]>>
icr(0.19.4) > tree1.root.key
 => ""
icr(0.19.4) > tree1.add "/members/:id/edit", :member_edit
 => #<Radix::Node(Symbol):0x105ba8d00 @payload=:member_edit, @priority=1, @key="/members/:id/edit", @placeholder=false, @children=[]>
icr(0.19.4) > tree1.root.key
 => "/members/:id/edit"
icr(0.19.4) > tree1.add "/members/:id/videos", :member_videos
 => nil
icr(0.19.4) > tree1.root.key
 => "/members/:id/"
icr(0.19.4) > tree1.add "/members/export", :members_export
 => nil
icr(0.19.4) > tree1.root.key
 => "/members/"
icr(0.19.4) > 
icr(0.19.4) > tree2 = Radix::Tree(Symbol).new
 => #<Radix::Tree(Symbol):0x10cd3dd60 @root=#<Radix::Node(Symbol):0x10cd3fbc0 @payload=nil, @priority=0, @key="", @placeholder=true, @children=[]>>
icr(0.19.4) > tree2.root.key
 => ""
icr(0.19.4) > tree2.add "/members/:id/edit", :member_edit
 => #<Radix::Node(Symbol):0x101041b80 @payload=:member_edit, @priority=1, @key="/members/:id/edit", @placeholder=false, @children=[]>
icr(0.19.4) > tree2.root.key
 => "/members/:id/edit"
icr(0.19.4) > tree2.add "/members/export", :members_export
 => nil
icr(0.19.4) > tree2.root.key
 => "/members/"
icr(0.19.4) > tree2.add "/members/:id/videos", :member_videos
Tried to place key ':id/videos' at same level as ':id/edit' (Radix::Tree::SharedKeyError)
[4444267922] *CallStack::unwind:Array(Pointer(Void)) +82
[4444267825] *CallStack#initialize:Array(Pointer(Void)) +17
[4444267784] *CallStack::new:CallStack +40
[4444253881] *raise<Radix::Tree::SharedKeyError>:NoReturn +25
[4444329154] *Radix::Tree(Symbol)@Radix::Tree(T)#add<String, Symbol, Radix::Node(Symbol)>:(Array(Radix::Node(Symbol)) | Symbol | Nil) +1234
[4444327877] *Radix::Tree(Symbol)@Radix::Tree(T)#add<String, Symbol>:(Array(Radix::Node(Symbol)) | Radix::Node(Symbol) | Symbol | Nil) +117
[4444253830] *__icr_exec__:(Array(Radix::Node(Symbol)) | Radix::Node(Symbol) | Symbol | Nil) +246
[4444219154] __crystal_main +1010
[4444253304] main +40
icr(0.19.4) > tree2.root.key
 => "/members/"

As the paths are added, the root key is shifted around causing the children to be shifted around. Maybe these children can just be sorted first before being parsed?

[luislavena]

Thank you for the detailed report @jwoertink!!! :heart: :heart: :heart:

The caveat mentioned in the README only applies when the named parameter name is different, example:

• /members/:id/edit
• /members/:email

But your case, :id is the same.

The problem is that code is comparing :id/edit against :id/videos like was a entire key, not considering the possibility of relocate the child node. The issue is around lines 133-150 of tree.cr

I'm might not be able to work on this until the weekend, but feel free to add comments take the pull request as a challenge :smile:

[luislavena]

Just a quick hint: looking at _same_key? logic, I think it shouldn't be checking that key_reader has been exhausted :wink:

[luislavena]

This is how the tree should look like:

# /members/
#         +-export      (:members_export)
#         \-:id/
#              +-videos (:members_videos)
#              \-edit   (:members_edit)

Cheers.

[luislavena]

And the spec could look something like this (haven't tested):

it "does allow same named parameters in different order of insertion" do
  tree = Tree(Symbol).new
  tree.add "/members/:id/edit", :member_edit
  tree.add "/members/export", :members_export
  tree.add "/members/:id/videos", :member_videos

  # /members/
  #         +-export      (:members_export)
  #         \-:id/
  #              +-videos (:members_videos)
  #              \-edit   (:members_edit)
  tree.root.key.should eq("/members/")
  tree.root.children.size.should eq(2)

  # first level children nodes
  tree.root.children[0].key.should eq("export")
  tree.root.children[1].key.should eq(":id/")

  # inner childrens
  nodes = tree.root.children[1].children
  nodes[0].key.should eq("videos")
  nodes[1].key.should eq("edit")
end

[jwoertink]

sweet! That puts me on the right track. I'll take a stab at it and let you know how it goes.

[jwoertink]

Well, I got my spec to pass. Unfortunately, there's like 3 others that are now broke. 😒

[luislavena]

Hello @jwoertink, no worries about that!

Understanding how Radix data structure works and this implementation is a bit challenging, even with all the comments and specs all around :sweat:

I've opened #10 including my spec and the changes to make this work.

Once specs passes going to merge and wrap another release so Kemal can update to use the new version.

Thank you for your report and your help figuring this out! :heart: :heart: :heart:

[vladfaust]

I'm not sure if it's related to this particular issue, point me if I'm wrong.

This:

icr(0.24.2) > tree = Radix::Tree(Symbol).new
 => #<Radix::Tree(Symbol):0x16aef00 @root=#<Radix::Node(Symbol):0x16b0f00 @payload=nil, @priority=0, @children=[], @kind=Normal, @key="", @placeholder=true>>
icr(0.24.2) > tree.add("/articles/:slug", :article)
 => #<Radix::Node(Symbol):0xf7beb0 @payload=:article, @priority=10, @children=[], @kind=Named, @key="/articles/:slug", @placeholder=false>
icr(0.24.2) > tree.add("/articles/:article_slug/comments/:comment_id", :comment)
 => nil
icr(0.24.2) > tree.find("/articles/how-to-train-your-dragon").found?
 => false
icr(0.24.2) > tree.find("/articles/how-to-train-your-dragon/comments/1").found?
 => false

I see that different same-level keys don't work, but I assume it should raise an error instead of swallowing silently and destroying previously declared paths. Such a weird (for me) behavior is revealed only when you try to actually .find, e.g. when doing integration testing.

[luislavena]

@vladfaust this appears to be a regression since two different keys (:slug and :article_slug) cannot be at the same level. Please open a separate issue so we can keep track of all open issues.

I don't have time for OSS in the upcoming 2 months to take a look into this. Played a bit with some ideas to change Radix and make it more easy to change, but nothing that reaches the same level of maturity as is today.

I believe someone forked and fixed those issues, but I cannot find the reference, will be great if they want to merge these changes or decide to maintain it instead.

Cheers.