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?