Consider providing a natural ordering for URLPattern objects

[wanderview]

In this twitter thread:

https://twitter.com/posva/status/1418470155579953153

It was pointed out having an ordering for patterns is helpful for routering framework.

I have a plan to provide an ordering for restricted patterns that are service worker scopes. This issue is to consider if there is a way to come up with a generalized ordering.

The big question in my mind would be how to treat custom regular expression groups. My inclination would be to treat them as equal to a full wildcard * in terms of specificity since we can't really tell how specific or not they are. (Inspecting a custom regexp to determine what its going to do is probably going to be too complex, etc.)

[wanderview]

Info on service worker scope ordering can be found in the explainer and design doc.

[wanderview]

If we expose an ordering here @domenic suggests the best way to do that would be an URLPattern.compare() static function.

[wanderview]

I think I have something that will work. I hope to have it in chrome canary this week for folks to try out.

[wanderview]

I have a prototype written and in review. It implements URLPattern.compare() static method that determines which pattern is "more specific". Here determining specificity means comparing a number of things.

First we prioritize components within the URLPattern from left to right right to left:

protocol < username < password < hostname < port < pathname < search < hash

Within each component we compare pattern strings "part by part".

This bit requires understanding how the parser works, but basically pattern strings get broken up into parts that represent fixed text or matching groups. Matching groups can also have fixed text prefix and suffix values associated with them. And both fixed text and matching groups can have modifiers that make them optional or repeat.

To compare two part objects we prioritize information as follows:

1. Part type is most important. A fixed text part is always considered more specific than regexp or wildcard. A regexp is considered more specific than a wildcard.
2. The modifier is next important. They are weighted as "none" > + > ? > *. So modifiers that still require at least one instance of the group are more specific than optional modifiers. Modifiers that allow at most one instance of a group are more specific than a repeating modifier.
3. The fixed text values in the part are considered next from left to right. This uses lexicographical sorting to determine specificity. So longer strings are more specific than shorter strings. z also happens to be more specific than a.

Finally, at the end of a list of parts we consider there to be a fixed text part with an empty string value. This anchors the end of the pattern so that /foo/ is more specific than /foo/*.

Some examples:

• /foo/:bar is more specific than /foo/*.
• /foo/:bar is more specific than /foo/:bar?.
• /foo/bar/* is more specific than /foo/*.
• /foo/bar/:baz is more specific than /foo/:baz/bar.
• /foo/([0-9]+) is more specific than /foo/*.
• */foo is more specific than *.

There are a couple of places where the algorithm can create unexpected results, though. In general, these might be a bit confusing, but I don't think they are harmful to using ordering for a router. Consider:

• /foo/bar is more specific than /foo/(bar) even though they match the exact same strings.
• /foo{/:bar/}baz is more specific than /foo/:bar/baz even though they match the exact same strings.
• Custom regular expressions are compared against each other lexicographically. This undoubtedly will create some non-optimal results, but it works better than I originally anticipated. For example, ([12]) is still considered more specific than ([123]) because ] is lexicographically greater than 3.

Thoughts? I hope to have something you can test against in canary chrome later this week. (The polyfill is not updated yet either.)

[wanderview]

I forgot to mention, URLPattern.compare(left, right) will return 1 if left is more specific, -1 if right is more specific, and 0 if they are considered equal. This means if you array.sort(URLPattern.compare) you will get an array with the least specific pattern first.

Will routing code, though, need things in the reverse order? While adding .reverse() after the sort is not hard, should we instead reverse the logic by default here?

[jeremyroman]

It wouldn't have been obvious to me that compare compared specificity. Maybe this should be URLPattern.compareSpecificity or similar?

Is this ordering supposed to provide certain properties useful to routing frameworks? This seems to naturally be a partial ordering rather than a total ordering, so it seems inevitable that there will be cases where two patterns aren't naturally more or less specific than one another but this algorithm makes a choice that may or may not be correct for the developer's use. e.g. http{s}?://*/* is more specific than *://www.google.com/search (because the protocol is).

It would be nice to know what they can rely on this ordering for and what they cannot.

[domenic]

First we prioritize components within the URLPattern from left to right:

I normally think of URLs as being "right to left" in the sense that their most-specific stuff is on the right. This might be related to what Jeremy was getting at with his http{s}?://*/* vs. *://www.google.com/search example.

What kind of cases would change if you flipped the prioritization here?

It wouldn't have been obvious to me that compare compared specificity. Maybe this should be URLPattern.compareSpecificity or similar?

I kind of like this; it's nice and explicit. The simple compare has a benefit of matching the new Temporal classes (example) but maybe it's not an obvious win.

The only thing we would lose out on there would be if, in the future, the JS spec does something special with the name compare (e.g., it introduces the spaceship operator and has it delegate to the compare static function), based on the Temporal precedent. But in that case it'd be easy enough to add an alias.

I'm curious what web devs think.

This seems to naturally be a partial ordering rather than a total ordering

It seems like you could still use a (-1, 0, 1) comparator function to create a useful partial ordering, just by returning 0 more often. I don't know when that'd be more or less useful though, or if there are natural points in Ben's algorithm above where you think we should not decide one is more specific than the other.

[wanderview]

I'm happy to change the name if folks think that is appropriate.

I originally conceived of the "more specific" algorithm for service worker scope processing. We need something like this there to select the correct service worker registration.

I had multiple folks involved with routing ask if this could be generalized and exposed. This was my attempt.

[wanderview]

I guess I had thought protocol was more specific than others because it determines how other components work, etc. For example, it changes how pathname parses.

I'm happy to reverse the logic around to be right-to-left, though. This part of my plan is the least thought out since we don't need multiple components for service workers.

In terms of partial vs total ordering, I feel we should make an ordering choice in as many cases as possible. It seems routing authors need to have some ordering and are looking for assistance in the pattern library to do this.

Right now I think the primary way you can end up with equality, but different inputs is:

1. Same pattern except different :foo names. We don't consider the name in specificity at all.
2. Various inputs that get normalized to the same thing; e.g. /foo{/:bar} is normalized to /foo/:bar, etc.

[wanderview]

Thinking about it, I see the point now how things are more specific on the right of the URL. I'll reverse the component ordering in the prototype.

[wanderview]

A couple more thoughts I had while cutting the grass this evening:

First, maybe its not accurate to say the proposal is comparing which is "more specific". After all, /reallylong is more specific than /short, yet the algorithm says /short is greater.

I think instead it would be more accurate to say URLPattern.compare() provides a mostly lexicographical ordering based on plain text in the pattern. When there is a difference that consists of matching groups and modifiers we try to pick the pattern that is more restrictive or specific.

Second, since we are unsure of the component prioritization for URLPattern.compare(left, right), maybe we should offer a more granular primitive instead. We could instead provide URLPattern.compareComponent(component, left, right) that compares a single component within the patterns. So then you could do array.sort(URLPattern.compare.bind('pathname')).

We could offer something that matches multiple components like array.sort(URLPattern.compareComponents.bind(['pathname', 'hostname'])), but I'm inclined not to yet. This could be build in user space on top of compareComponent().

WDYT?

[wesleytodd]

Is this ordering supposed to provide certain properties useful to routing frameworks?

To me, this is the most important question to answer. I think that considering the direction of backend frameworks is really important here. In my experience, maintaining parity between your frontend and backend routing is highly valuable to end users.

---

One thing about this approach which is concerning to me is that existing frameworks (specifically on the backend) do not implement a route specificity sorting method exactly like this. Fastfy has a concept which is similar, but only operates on a single segment at a time which enables the radix tree matching approach. This proposal goes in a different direction (I understand why it does) which makes me wonder how this would work with FE & BE routing. Specifically I am thinking about BE rendered SPAs which use FE routing after (a rather common approach these days).

We could instead provide URLPattern.compareComponent(component, left, right) that compares a single component within the patterns.

This would be more in line with how fastify does it, but still seems to lack a definition of path segments?

---

Additionally, I think that the prior art in this area is mostly based on frameworks using declaration order and not a platform defined sorting algo. The only example I have experience with which uses a similar specificity sorting algo is nginx. Unfortunately I have seen this cause confusion and difficulty when debugging, especially for beginners. Maybe I just need to see it done "well", and to that end it would help to present existing implementations like this where it is a well regarded solution to this problem.

I think the considerations between a framework adopting a pattern (like express or react router did with path-to-regexp did) as compared to what the web platform can adopt are quite different. In my initial reading of this, I am concerned that this proposal is too specific and might be better left to userland implementations depending on the router approach.

[wanderview]

@wesleytodd can you provide an example where the path segment approach provides a different ordering? The example in the link you provided would result in the same ordering with my proposed algorithm.

We do have a concept of "segment" in URLPattern for pathnames and hostnames. In the pathname the segment separator is / and in hostnames the segment separator is .. The :name groups by default match to the end of a segment. This concept is not used for any other features right now, though.

And thank you for the link. In terms of matching groups my proposal is similar to that, but weights regular expressions differently. That link has "parametric" and "wildcard" greater than custom regexp groups. My proposal is for custom regexp groups to be greater than parametric and wildcard since they seem likely to be more restrictive.

In my experience, maintaining parity between your frontend and backend routing is highly valuable to end users.

I agree you would not want your FE and BE behavior to be out of sync. It seems, though, like this will be an issue any time you choose a different pattern matching construct in FE and BE. At least for folks using nodejs, URLPattern will offer an isomorphic way to work with patterns across FE and BE. There has also been some interest in implementing URLPattern in other server side implementations. (#58 (comment))

Additionally, I think that the prior art in this area is mostly based on frameworks using declaration order and not a platform defined sorting algo.

Just because we expose URLPattern.compare() it doesn't mean a js framework could not provide their own, different ordering. You can use URLPattern and not use compare().

I am concerned that this proposal is too specific and might be better left to userland implementations depending on the router approach.

Normally I would agree and not expose this for now. But I've gotten feedback that ordering would be welcome for client side routing. (#45) In addition, its difficult to implement this kind of ordering in user space without access to the internal representation of the pattern string. You would need to implement your own parser which starts to defeat the goal of providing this API in the platform.

Since its use is optional and there are folks who would use it, I'm inclined to expose the comparison feature.

[wanderview]

@posva Do you have an opinion on the proposed algorithm in #61 (comment) and #61 (comment)? How does this compare to the route ranking that is done for Vue?

[wesleytodd]

The example in the link you provided would result in the same ordering with my proposed algorithm

Sorry, my point there might have been unclear. I meant more that frameworks like Fastify might be unlikely to use this compare functionality because they are matching single segments in a radix tree data structure for performance. So this would likely introduce discrepancies if a FE framework was only relying on this but the BE framework was doing something else. I pinged folks from that project on twitter, so if you think this is worth discussing more I am sure they would not mind jumping in here to give more opinions.

URLPattern will offer an isomorphic way to work with patterns across FE and BE.

My goal with bringing up is that I believe that without input from framework maintainers, there are details which might make this never a reality. I don't think we would ever change express to use a route sorting mechanism, and if other more modern framework authors also would not, then I don't see this being viable.

There has also been some interest in implementing URLPattern in other server side implementations.

To be clear, I LOVE the idea of URLPattern. I am specifically talking about the ordering proposal in this issue. FWIW, I would absolutely support express moving toURLPattern under the hood. As mentioned in the twitter thread, I think getting input from Fastify folks would be great because it deviates more from the direction this repo takes (obviously since this was based on path-to-regexp it is inline with express' approach).

You can use URLPattern and not use compare()

This is what I meant about a difference between what the platform provides and what a framework does. It has been my experience that something landing in the platform provides a strong incentive for users to start asking it to be used in the other tools they use. Often times that is because they do not understand the complexity involved or the reasons for the direction the tool/framework took. If we can stop that from happening with this it would, IMO, be a good thing.

its difficult to implement this kind of ordering in user space without access to the internal representation of the pattern string.

I would love to know more about this. Honestly I think what you describe here with exposing this would be good even if it was not related to this. I have many times had to write tooling to dig deep into the express router and I know most metrics implementations like it when there is a nice digestible "route" string or data structure.

But I've gotten feedback that ordering would be welcome for client side routing.

Totally understand the sentiment here. If I worked on a framework that used a sorting approach to routes, then I would see this proposal and think the same thing. IMO this might be a trap of the "user first" approach. I would love to see a good write up of a platform which has this and how end users have liked it.

I am only familiar with how nginx uses specificity to order route matching, and I have spent hours debugging it before. I am not sure that it is bad for beginners, but I remember trying to help a team mate who was less familiar with nginx than I and it was pretty confusing to explain how they do it.

I also think that up leveling a feature to the platform without multiple successful userland implementations is tough and prone to mistakes. Again, maybe there are more than I am unaware of, so happy to be proven wrong here.

[wanderview]

@wesleytodd Again, if you have an example where the segment-based approach results in a different ordering it would be great to share it. Right now I believe my algorithm is achieving roughly the same behavior if not the same behavior. The only difference I see right now is how URLPattern is weighing custom regexp at a higher priority than fastify.

This is what I meant about a difference between what the platform provides and what a framework does. It has been my experience that something landing in the platform provides a strong incentive for users to start asking it to be used in the other tools they use.

I'm not sure I agree with this concern. Over the years there have been plenty of features added to the platform that never saw adoption. Getting added to the platform does not generally make developers use it unless the feature actually provides value.

If this feature provides value, maybe downstream devs will ask for it to be supported. If a framework author feels its the wrong choice, though, they should be able to provide an argument for why its the wrong fit. Again, we seem to see people adopt platform features when they provide value and not just because they are there.

I would love to know more about this. Honestly I think what you describe here with exposing this would be good even if it was not related to this. I have many times had to write tooling to dig deep into the express router and I know most metrics implementations like it when there is a nice digestible "route" string or data structure.

Exposing the internal representation is not something I want to consider right now. We need the flexibility to change it while we continue to evolve the API. In addition, it would be a lot of additional exposed complexity that would need solid use cases to justify.

I am only familiar with how nginx uses specificity

I tried to clarify, but the ordering is not really by specificity. Its more of a lexicographical sort similar to the one you linked to for fastify.

I also think that up leveling a feature to the platform without multiple successful userland implementations is tough and prone to mistakes. Again, maybe there are more than I am unaware of, so happy to be proven wrong here.

Well, I am trying to gather feedback from user space ordering solution. This feature was requested by @posva on the Vue team and I'm hoping they will tell us how it compares to their route ranking system and if it will work for Vue's use cases. I think the proposed algorithm is also very similar to the one you linked from fastify. (IMO splitting on segment boundaries is really more of an implementation detail, but happy to see a counter example.)

And again, I don't think this is a feature that user land can implement for URLPattern specifically without basically shipping the entire polyfill ever time. In other words they would have to sacrifice the benefit of having it in the platform. That means user land comparison implementations would likely never be realized. Folks that need them would just stick to other non-URLPattern solutions instead.

Ultimately I expect any ordering solution will fail to be a good fit for some system or framework out there. I don't think we can get perfect coverage. I think its reasonable, though, to collect as much feedback as we can and ship something we expect to work for many cases. In particular if the solution is something the browser needs internally anyway, the cost benefit would seem towards exposing it. We can always expose additional comparison routines in the future if there is strong feedback indicating they are needed.

[wesleytodd]

Again, if you have an example where the segment-based approach results in a different ordering

My point was specifically not if it produced the same end, it was "might be unlikely to use this compare functionality". If I am wrong here, and they (find-my-way) would use it then this point is moot. If my suspicions are correct, then I think collaborating with those folks would improve the end product.

Exposing the internal representation is not something I want to consider right now. We need the flexibility to change it while we continue to evolve the API.

Having written a bit of tooling related to this space, having proper introspection api's is a big help. I think this is only loosely related to this issue, so I will not try to make the argument here.

I am trying to gather feedback from user space ordering solution

Yep, that is why I commented. This is my feedback 😄. In case it matters, this is feedback from someone on both the express and restify core teams and who helped found the node.js web server frameworks team. I am a big 👍 on the URLPattern and a 😐 on this addition.

Anyway, while I am not sure my feedback has been heard and understood, I am not strongly involved or opinionated here to continue trying to push this conversation. My recommendation is to farm for feedback on this proposal with more than just one contributor to one framework (starting with find-my-way as it is the most popular corollary on the server side).

[wanderview]

I appreciate the feedback. The link to that find-my-way ordering algorithm is definitely useful. Again, I think the comparison I am proposing here is roughly equivalent to what find-my-way is doing.

You may also find #42 of interest where the find-my-way radix tree implementation was raised as a performance benefit. I think similar optimizations will still be possible in URLPattern and I plan to work on them soon as we will need a non-regexp matching algorithm for integration with service workers.

I do want to push back, though, on the "if find-my-way won't adopt, then its bad" argument. This effort is primarily focused on providing a web platform API. The goals and constraints of the web platform are different than the goals and constraints of server side. Reducing match speeds by 100 microseconds is insignificant for web platform use cases, but definitely matters for the server as it adds up to reduced compute costs. Therefore its completely reasonable and possible that server side will converge on different solutions than client side.

That being said, I think aligning with find-my-way if possible would be great and I'm happy to investigate that more.

[wesleytodd]

I do want to push back, though, on the "if find-my-way won't adopt, then its bad" argument.

I don't think I said "bad". I would go as far as saying "less optimal" for this proposal. Having maintained multiple systems where the backend routing semantics differed from the frontend, I do think that UX is "bad" and if it can be avoided in the use cases where we know JS is used on both sides, then I think usable in both contexts is a reasonable bar to set for platform api's.

I think similar optimizations will still be possible in URLPattern

Learning from the prior art here, I would personally put this front and center. From an implementation detail standpoint, I would only resort to regex under the hood after other more performant matching can be done. Even express has special escape's for avoiding regexp in path-to-regexp where it can because of performance.

That being said, I think aligning with find-my-way if possible would be great and I'm happy to investigate that more.

Great! that was really my only goal. I wanted to bring the technical concerns to back up that as a next step, but the real goal of giving this feedback was to push more collaboration here with those folks.

[wanderview]

The proposed (but not final) URLPattern.compareComponent() is now available in chrome canary 94.0.4590.0. If you have time and interest, please give it a try and let us know what you think.

Note, you also have to enable chrome://flags/#enable-experimental-web-platform-features before you can use URLPattern.

Edit: Note, this is not available in the polyfill yet.

[wanderview]

I looked a bit at find-my-way. I had a bit of a misunderstanding previously about where the radix tree came into things. I was thinking it was used to perform the match of a single pattern string against a URL, but it appears to be used to quickly find a matching pattern string out of a collection of routes.

That is certainly related to ordering, but it also suggests it might be a feature we want to add on URLPatternList or another container type. So we can discuss that more on #30.

[posva]

@posva Do you have an opinion on the proposed algorithm in #61 (comment) and #61 (comment)? How does this compare to the route ranking that is done for Vue?

I'm sorry @wanderview, I simply didn't see the mention 😓 I think it's too late but I will still comment my thoughts:

The priority proposed in #61 (comment) seems good 👍

Regarding #61 (comment): in the case of SPA, only the pathname matters (although having the search and hash are a really nice addition). The user is still responsible for creating a list of mutually exclusive patterns, e.g. it makes no sense to add /users/:id and /users/:uid, same goes for custom regexp /users/:id(\d+) and /users/:id([0-9a-f]+). So having inconsistencies when such conflicting patterns are provided is IMO fine.