Issues with key length, insertion order, named and glob parameters during lookup

[luislavena]

Originally reported under kemalcr/kemal#293, the usage of named parameters seems to be affected by the order in which new keys are inserted in the tree when part of it is shared across entries.

require "./src/radix"

class Radix::Node
  # override for testing
  def to_s(io, nesting = 0)
    # format: # (priority) (indent) key
    io << ("# (%2d) " % priority) << (" " * nesting) << key << '\n'
    children.each do |child|
      child.to_s(io, nesting + key.size)
    end
  end
end

tree = Radix::Tree(Symbol).new
tree.add "/one/:id", :one
tree.add "/one-longer/:id", :two

# show tree
puts tree.root.to_s(STDOUT, 0)
# ( 4) /one
# (-1)     /:id
# (-1)     -longer/:id

result = tree.find "/one-longer/10"

# expected to be `true`
puts result.found? # => false

Now, when keys are added in reverse order (longer first), lookup works since key is properly inserted before the other:

tree = Radix::Tree(Symbol).new
tree.add "/one-longer/:id", :two
tree.add "/one/:id", :one

puts tree.root.to_s(STDOUT, 0)
# ( 4) /one
# (-1)     -longer/:id
# (-1)     /:id

result = tree.find "/one-longer/10"

# works, result is `true`
puts result.found? # => true

This is caused by two nodes having the same priority, so insertion order wins 😞

It is required that we apply the same priority sorting to named and glob parameters as we apply to other keys: the longer the key, the higher it ranks.

Since nodes that contains named and glob keys might interfere with the lookup, they must remain lower than regular ones.

Need to review the prioritization technique to accommodate this change. 🤔