Thanks @dtolnay! I've updated the pre-rfc.
I don't actually think the brute force is a problem: It can be structured as:
- Look for the name directly
- If not, traverse the tree recursively, splitting whenever the dash and slash are both extant in the tree
The brute force exponential growth is only a problem if in fact there are crates sharing prefixes with the same names modulo dashes/underscores that have a large number of separators. I.e. you'd need foo-bar-baz-quux-1, foo-bar-baz_quux-2, foo-bar_baz-quux-3 and so on to all exist. This is unlikely and an attempt to set something like this up would itself require an exponential number of automated publishes and would be a violation of the crates.io policy. Furthermore, such exponential explosions are already possible in Cargo if you allow a large number of automated publishes and create a deep dependency tree.