Prefix wildcard matching is required

[rakyll]

Currently, govanityurls looks for an exact prefix match for the paths provided in the configuration file.

host: my.org

paths:
   - /example/helloworld
        repo: ....
   - /
        repo: .... 

If user asks for my.org/x, govanityurls return a 404 instead of matching it with the second rule.

What's expected is that we should match /x with the / rule.

[odeke-em]

I once encountered this problem when deciding the most appropriate matching paths and directories to serve for a cloud service during cache misses based off their prefix.

I recall the algorithm that I used, it seems simple enough to find the most common prefix i.e.:

• Given rules/paths H
• Given a query Q
• Sort H by length of each element -- for fast exact search using binary search

1. Search for the queried rule with a binary search over H. If we can find it, return it, else goto 2.
2. We need to match the closest/shortest prefix relative to the query. For a prefix, we need len(rule) < len(Q), giving us items pR
3. For each pRi in pR, trim it from Q, recording the length and pRI if shorter than known
4. The shortest trimmed remainder from TrimPrefix(Q, pRi) is the closest host

With some runnable code at https://gist.github.com/odeke-em/4101fc01adaea3bfead1241e561fcc61, it can further be optimized but that serves the purpose I believe.