Relative priority of routing rules can change from unrelated rules

[sdegueldre]

Titular issue

Have two rules with a dynamic segment using different converters with the same weight in your application. When a request comes in that could match both rules, it matches the first because it was registered first, as documented:

Rules may end up with the same priority, by having static parts with the same length, and dynamic parts with the same weight, in the same positions. In this case, sorting is stable, so rules added earlier take priority.

Add a new rule in your application before the first (eg for code organization reasons), this rule should have a dynamic segment in the same place as both of the existing rules, and use the same converter as the second rule, but otherwise not match the incoming request's URL.

Incoming requests with the same URL as before now start matching the second rule, despite the fact that it has the same priority as the first rule and that the first rule was added earlier.

Reproduction:

def test_consistent_relative_priority():
    rule_1 = r.Rule("/<dummy:value>", endpoint="rule_1")
    rule_2 = r.Rule("/<string:value>", endpoint="rule_2")
    map = r.Map(
        [
            rule_1,
            rule_2,
        ], converters={'dummy': r.BaseConverter}
    )
    adapter = map.bind("example.org", "/")
    assert adapter.match("/foo") == ("rule_1", { "value": "foo"})

    map = r.Map(
        [
            r.Rule("/<string:value>/no_match", endpoint="no_match"),
            rule_1.empty(),
            rule_2.empty(),
        ], converters={'dummy': r.BaseConverter}
    )
    adapter = map.bind("example.org", "/")
    assert adapter.match("/foo") == ("rule_1", { "value": "foo"}) # Fails: rule_2 matches instead

Note that the dummy converter is just a stand-in for any custom converter with the default weight of 100. If both routes use the string converter in the first position, the issue does not occur because the rules are merged when being added to the map's matcher.

Expected behavior:
Non-matching rules should not affect the relative priority of following rules.

Environment:

• Python version: 3.12.3
• Werkzeug version: 3.0.1 -> main

---

Related issue

(let me know if I should create a separate issue for this, I'm putting this here because the root cause seems identical to me)

More specific rules will only have priority over more general ones if they use the same converter. When using different converters of the same weight, rules that have the common prefix that was registered first (regardless of the order the actual rules were registered, as demonstrated above) will have priority.

Reproduction:

def test_cross_converter_rule_specificity():
    map = r.Map(
        [
            r.Rule("/<string:value>/<path:path>", endpoint="less_specific"),
            r.Rule("/<string:value>/bar", endpoint="more_specific"),
        ]
    )
    adapter = map.bind("example.org", "/")
    assert adapter.match("/foo/bar") == ("more_specific", { "value": "foo"})

    map = r.Map(
        [
            r.Rule("/<string:value>/<path:path>", endpoint="less_specific"),
            r.Rule("/<dummy:value>/bar", endpoint="more_specific"),
        ], converters={'dummy': r.BaseConverter}
    )
    adapter = map.bind("example.org", "/")
    assert adapter.match("/foo/bar") == ("more_specific", { "value": "foo"}) # Fails: less_specific matches instead

Cause:

I'm not super familiar with the code base but from my understanding, this is caused by the way the StateMachineMatcher merges rules as they're being added, in particular:

# matcher.py L46-49
for test_part, new_state in state.dynamic:
    if test_part == part:
        state = new_state
        break

This code means that when adding a new rule, it takes the priority of whatever existing rule is already registered with which it shares a prefix (for dynamic parts, converters that yield the same RulePart).

Possible fixes

I'm not sure what the proper fix would be, as I'm not super familiar with the codebase and exact implications of each fix, but here are a few suggestions in increasing order of completeness and complexity:

1. Document that converters themselves have a priority, and sort rule parts by weight and by order in which converters were registered on the routing map. This means that custom converters always have lower priority than default converters with the same weight. With this, in the first test, rule_2 will always match regardless of the rule order.
   Alternatively, if we want custom converters to win over default ones, it could be in reverse registration order: most recent converter wins, though this goes against the "first wins" principle applied elsewhere.

2. When merging rules in the state machine, only merge the RulePart if it's the same as the last dynamic segment currently known, this fixes the first test case, but not the second, and is more of a band-aid fix, it gives us the priority-by-order property but doesn't fix the specificity problem, and this will result in less merging and likely more expensive matching in pathological cases where users are registering many rules with different converters of the same priority in the same segment in a staggered manner.

3. The most general and complete fix that fixes both tests: merge dynamic parts of the same weight, even if they have different rules, but that means that State.dynamic would now need to be a map of the form {converter_weight: Array[RulePart]}. This has more profound implications w.r.t. how the state machine evaluates matches, as you would in principle need to take multiple state transitions in "parallel" for converters of the same weight, and end up with a sort of DFS/BFS hybrid through the state graph.

[davidism]

@pgjones any thoughts on this? I'm having a hard time following the code to figure it out.

[pgjones]

I think the issue here is your dummy converter as it looks to be the same as a string converter, but is in fact subtly different (regex is different). Ideally I think the Map should recognise the duplicate rule but it can't as the regex doesn't match. I think the best solution would have been for the Map to error if multiple converters of the same weight are added but this isn't workable as the default converters have equal weights.
Is this causing you an error, if so does adjusting the weighting fix it?

[sdegueldre]

@pgjones I used a dummy converter to showcase the issue. In practice, as explained in the issue, I was using a custom converter that has a substantially different regex, it was simply not relevant for the repro so I used the BaseConverter as a stand-in.

A more compelling example is to simply sub in the AnyConverter instead of the BaseConverter dummy:

def test_consistent_relative_priority():
    rule_1 = r.Rule("/<any(foo, bar):value>", endpoint="rule_1")
    rule_2 = r.Rule("/<string:value>", endpoint="rule_2")
    map = r.Map(
        [
            rule_1,
            rule_2,
        ]
    )
    adapter = map.bind("example.org", "/")
    assert adapter.match("/foo") == ("rule_1", {"value": "foo"})

    map = r.Map(
        [
            r.Rule("/<string:unrelated>/no_match", endpoint="no_match"),
            rule_1.empty(),
            rule_2.empty(),
        ]
    )
    adapter = map.bind("example.org", "/")
    assert adapter.match("/foo") == (
        "rule_1",
        {"value": "foo"},
    )  # Fails: rule_2 matches instead

By all accounts, the AnyConverter is more specific than the UnicodeConverter, its weight probably should be lower, which fixes the issue, but that's a pretty big breaking change, and my situation is the same: I have existing custom converters that have the default weight and that are widely used. Changing their weight is likely to affect route matching on the entire project is subtle ways that are difficult to predict, so it's not really an option.

What I ended up doing was creating a copy of the existing custom converter that has a lower weight and used that instead in that specific place so as to not completely change route priority for the entire app. That being said the current behavior was surprising and difficult to debug and attribute.

As I said, I'm pretty sure it's possible for this to be fixed in place without generating errors, though it's a pretty involved change in the matcher. Here is an example of something you might want to do, although I admit it's a little bit contrived:

def test_consistent_relative_priority_uuid():
    # if we have a uuid at the end, we want to match the first part of the url as a string
    rule_0 = r.Rule("/<string:str>/<uuid:id>", endpoint="rule_0")
    rule_1 = r.Rule("/<uuid:id>/<string:str>", endpoint="rule_1")
    # if it's a single segment we want to match it as a UUID if possible
    rule_2 = r.Rule("/<uuid:id>", endpoint="rule_2")
    rule_3 = r.Rule("/<string:str>", endpoint="rule_3")
    map = r.Map(
        [
            rule_0,
            rule_1,
            rule_2,
            rule_3,
        ]
    )
    adapter = map.bind("example.org", "/")
    assert adapter.match(
        "/00000000-0000-0000-0000-000000000000/00000000-0000-0000-0000-000000000000"
    ) == (
        "rule_0",
        {
            "id": uuid.UUID("00000000-0000-0000-0000-000000000000"),
            "str": "00000000-0000-0000-0000-000000000000",
        },
    )
    assert adapter.match("/00000000-0000-0000-0000-000000000000/not_a_uuid") == (
        "rule_1",
        {
            "id": uuid.UUID("00000000-0000-0000-0000-000000000000"),
            "str": "not_a_uuid",
        },
    )
    assert adapter.match("/00000000-0000-0000-0000-000000000000") == (
        "rule_2",
        {
            "id": uuid.UUID("00000000-0000-0000-0000-000000000000"),
        },
    )
    assert adapter.match("/not_a_uuid") == (
        "rule_1",
        {
            "str": "not_a_uuid",
        },
    )

If the UUID matcher had a lower weight, it is impossible to match "uuid at end" with higher priority than "uuid at beginning". But with the current state of the code, matching "uuid at end" with higher priority than "uuid at beginning" makes it subsequently impossible to match single uuid with higher priority than string.

Note that this is already the case for lower weight converters like int for example so it may be considered an acceptable limitation, ie /<int:num>/<string:str> always has higher priority than /<string:str>/<int:num>, since lower weight parts earlier in the URL have priority regardless of what comes after, eg even /<string:str>/50 has lower priority than /<int:num>/<path:subpath> even though I would argue it's a lot more specific. All that to say that maybe the above use case doesn't have to be supported and if you want to do the above you just use a very general converter (like string) in each segment then handle "routing"/dispatch by hand in the endpoint in those advanced cases.

(note that all my examples can be slotted as-is into test_routing.py and be ran with the test runner, if that helps)