We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
2.2.0 breaks werkzeug.routing.ValidationError import
```
(venv-test) $ pip install werkzeug
Collecting werkzeug
  Downloading Werkzeug-2.2.0-py3-none-any.whl (232 kB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 232.2/232.2 KB 3.5 MB/s eta 0:00:00
Collecting MarkupSafe>=2.1.1
  Using cached MarkupSafe-2.1.1-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (25 kB)
Installing collected packages: MarkupSafe, werkzeug
Successfully installed MarkupSafe-2.1.1 werkzeug-2.2.0
(venv-test) $ python
Python 3.10.4 (main, Jun 29 2022, 12:14:53) [GCC 11.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from werkzeug.routing import ValidationError
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ImportError: cannot import name 'ValidationError' from 'werkzeug.routing' (/tmp/venv-test/lib/python3.10/site-packages/werkzeug/routing/__init__.py)
```

This is a documented API for 2.2, e.g. https://werkzeug.palletsprojects.com/en/2.2.x/routing/#custom-converters example code.

Environment:

- Python version: 3.10
- Werkzeug version: 2.2.0


--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `src/werkzeug/routing/__init__.py`
Content:
```
1 """When it comes to combining multiple controller or view functions
2 (however you want to call them) you need a dispatcher. A simple way
3 would be applying regular expression tests on the ``PATH_INFO`` and
4 calling registered callback functions that return the value then.
5 
6 This module implements a much more powerful system than simple regular
7 expression matching because it can also convert values in the URLs and
8 build URLs.
9 
10 Here a simple example that creates a URL map for an application with
11 two subdomains (www and kb) and some URL rules:
12 
13 .. code-block:: python
14 
15     m = Map([
16         # Static URLs
17         Rule('/', endpoint='static/index'),
18         Rule('/about', endpoint='static/about'),
19         Rule('/help', endpoint='static/help'),
20         # Knowledge Base
21         Subdomain('kb', [
22             Rule('/', endpoint='kb/index'),
23             Rule('/browse/', endpoint='kb/browse'),
24             Rule('/browse/<int:id>/', endpoint='kb/browse'),
25             Rule('/browse/<int:id>/<int:page>', endpoint='kb/browse')
26         ])
27     ], default_subdomain='www')
28 
29 If the application doesn't use subdomains it's perfectly fine to not set
30 the default subdomain and not use the `Subdomain` rule factory. The
31 endpoint in the rules can be anything, for example import paths or
32 unique identifiers. The WSGI application can use those endpoints to get the
33 handler for that URL.  It doesn't have to be a string at all but it's
34 recommended.
35 
36 Now it's possible to create a URL adapter for one of the subdomains and
37 build URLs:
38 
39 .. code-block:: python
40 
41     c = m.bind('example.com')
42 
43     c.build("kb/browse", dict(id=42))
44     'http://kb.example.com/browse/42/'
45 
46     c.build("kb/browse", dict())
47     'http://kb.example.com/browse/'
48 
49     c.build("kb/browse", dict(id=42, page=3))
50     'http://kb.example.com/browse/42/3'
51 
52     c.build("static/about")
53     '/about'
54 
55     c.build("static/index", force_external=True)
56     'http://www.example.com/'
57 
58     c = m.bind('example.com', subdomain='kb')
59 
60     c.build("static/about")
61     'http://www.example.com/about'
62 
63 The first argument to bind is the server name *without* the subdomain.
64 Per default it will assume that the script is mounted on the root, but
65 often that's not the case so you can provide the real mount point as
66 second argument:
67 
68 .. code-block:: python
69 
70     c = m.bind('example.com', '/applications/example')
71 
72 The third argument can be the subdomain, if not given the default
73 subdomain is used.  For more details about binding have a look at the
74 documentation of the `MapAdapter`.
75 
76 And here is how you can match URLs:
77 
78 .. code-block:: python
79 
80     c = m.bind('example.com')
81 
82     c.match("/")
83     ('static/index', {})
84 
85     c.match("/about")
86     ('static/about', {})
87 
88     c = m.bind('example.com', '/', 'kb')
89 
90     c.match("/")
91     ('kb/index', {})
92 
93     c.match("/browse/42/23")
94     ('kb/browse', {'id': 42, 'page': 23})
95 
96 If matching fails you get a ``NotFound`` exception, if the rule thinks
97 it's a good idea to redirect (for example because the URL was defined
98 to have a slash at the end but the request was missing that slash) it
99 will raise a ``RequestRedirect`` exception. Both are subclasses of
100 ``HTTPException`` so you can use those errors as responses in the
101 application.
102 
103 If matching succeeded but the URL rule was incompatible to the given
104 method (for example there were only rules for ``GET`` and ``HEAD`` but
105 routing tried to match a ``POST`` request) a ``MethodNotAllowed``
106 exception is raised.
107 """
108 from .converters import AnyConverter
109 from .converters import BaseConverter
110 from .converters import FloatConverter
111 from .converters import IntegerConverter
112 from .converters import PathConverter
113 from .converters import UnicodeConverter
114 from .converters import UUIDConverter
115 from .exceptions import BuildError
116 from .exceptions import NoMatch
117 from .exceptions import RequestAliasRedirect
118 from .exceptions import RequestPath
119 from .exceptions import RequestRedirect
120 from .exceptions import RoutingException
121 from .exceptions import WebsocketMismatch
122 from .map import Map
123 from .map import MapAdapter
124 from .matcher import StateMachineMatcher
125 from .rules import EndpointPrefix
126 from .rules import parse_converter_args
127 from .rules import Rule
128 from .rules import RuleFactory
129 from .rules import RuleTemplate
130 from .rules import RuleTemplateFactory
131 from .rules import Subdomain
132 from .rules import Submount
133
```

Path: `src/werkzeug/routing/matcher.py`
Content:
```
1 import re
2 import typing as t
3 from dataclasses import dataclass
4 from dataclasses import field
5 
6 from .converters import ValidationError
7 from .exceptions import NoMatch
8 from .exceptions import RequestAliasRedirect
9 from .exceptions import RequestPath
10 from .rules import Rule
11 from .rules import RulePart
12 
13 
14 class SlashRequired(Exception):
15     pass
16 
17 
18 @dataclass
19 class State:
20     """A representation of a rule state.
21 
22     This includes the *rules* that correspond to the state and the
23     possible *static* and *dynamic* transitions to the next state.
24     """
25 
26     dynamic: t.List[t.Tuple[RulePart, "State"]] = field(default_factory=list)
27     rules: t.List[Rule] = field(default_factory=list)
28     static: t.Dict[str, "State"] = field(default_factory=dict)
29 
30 
31 class StateMachineMatcher:
32     def __init__(self, merge_slashes: bool) -> None:
33         self._root = State()
34         self.merge_slashes = merge_slashes
35 
36     def add(self, rule: Rule) -> None:
37         state = self._root
38         for part in rule._parts:
39             if part.static:
40                 state.static.setdefault(part.content, State())
41                 state = state.static[part.content]
42             else:
43                 for test_part, new_state in state.dynamic:
44                     if test_part == part:
45                         state = new_state
46                         break
47                 else:
48                     new_state = State()
49                     state.dynamic.append((part, new_state))
50                     state = new_state
51         state.rules.append(rule)
52 
53     def update(self) -> None:
54         # For every state the dynamic transitions should be sorted by
55         # the weight of the transition
56         state = self._root
57 
58         def _update_state(state: State) -> None:
59             state.dynamic.sort(key=lambda entry: entry[0].weight)
60             for new_state in state.static.values():
61                 _update_state(new_state)
62             for _, new_state in state.dynamic:
63                 _update_state(new_state)
64 
65         _update_state(state)
66 
67     def match(
68         self, domain: str, path: str, method: str, websocket: bool
69     ) -> t.Tuple[Rule, t.MutableMapping[str, t.Any]]:
70         # To match to a rule we need to start at the root state and
71         # try to follow the transitions until we find a match, or find
72         # there is no transition to follow.
73 
74         have_match_for = set()
75         websocket_mismatch = False
76 
77         def _match(
78             state: State, parts: t.List[str], values: t.List[str]
79         ) -> t.Optional[t.Tuple[Rule, t.List[str]]]:
80             # This function is meant to be called recursively, and will attempt
81             # to match the head part to the state's transitions.
82             nonlocal have_match_for, websocket_mismatch
83 
84             # The base case is when all parts have been matched via
85             # transitions. Hence if there is a rule with methods &
86             # websocket that work return it and the dynamic values
87             # extracted.
88             if parts == []:
89                 for rule in state.rules:
90                     if rule.methods is not None and method not in rule.methods:
91                         have_match_for.update(rule.methods)
92                     elif rule.websocket != websocket:
93                         websocket_mismatch = True
94                     else:
95                         return rule, values
96 
97                 # Test if there is a match with this path with a
98                 # trailing slash, if so raise an exception to report
99                 # that matching is possible with an additional slash
100                 if "" in state.static:
101                     for rule in state.static[""].rules:
102                         if (
103                             rule.strict_slashes
104                             and websocket == rule.websocket
105                             and (rule.methods is None or method in rule.methods)
106                         ):
107                             raise SlashRequired()
108                 return None
109 
110             part = parts[0]
111             # To match this part try the static transitions first
112             if part in state.static:
113                 rv = _match(state.static[part], parts[1:], values)
114                 if rv is not None:
115                     return rv
116             # No match via the static transitions, so try the dynamic
117             # ones.
118             for test_part, new_state in state.dynamic:
119                 target = part
120                 remaining = parts[1:]
121                 # A final part indicates a transition that always
122                 # consumes the remaining parts i.e. transitions to a
123                 # final state.
124                 if test_part.final:
125                     target = "/".join(parts)
126                     remaining = []
127                 match = re.compile(test_part.content).match(target)
128                 if match is not None:
129                     rv = _match(new_state, remaining, values + list(match.groups()))
130                     if rv is not None:
131                         return rv
132             return None
133 
134         try:
135             rv = _match(self._root, [domain, *path.split("/")], [])
136         except SlashRequired:
137             raise RequestPath(f"{path}/") from None
138 
139         if self.merge_slashes and rv is None:
140             # Try to match again, but with slashes merged
141             path = re.sub("/{2,}?", "/", path)
142             try:
143                 rv = _match(self._root, [domain, *path.split("/")], [])
144             except SlashRequired:
145                 raise RequestPath(f"{path}/") from None
146             if rv is None:
147                 raise NoMatch(have_match_for, websocket_mismatch)
148             else:
149                 raise RequestPath(f"{path}")
150         elif rv is not None:
151             rule, values = rv
152 
153             result = {}
154             for name, value in zip(rule._converters.keys(), values):
155                 try:
156                     value = rule._converters[name].to_python(value)
157                 except ValidationError:
158                     raise NoMatch(have_match_for, websocket_mismatch) from None
159                 result[str(name)] = value
160             if rule.defaults:
161                 result.update(rule.defaults)
162 
163             if rule.alias and rule.map.redirect_defaults:
164                 raise RequestAliasRedirect(result, rule.endpoint)
165 
166             return rule, result
167 
168         raise NoMatch(have_match_for, websocket_mismatch)
169
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/src/werkzeug/routing/__init__.py b/src/werkzeug/routing/__init__.py
--- a/src/werkzeug/routing/__init__.py
+++ b/src/werkzeug/routing/__init__.py
@@ -112,6 +112,7 @@
 from .converters import PathConverter
 from .converters import UnicodeConverter
 from .converters import UUIDConverter
+from .converters import ValidationError
 from .exceptions import BuildError
 from .exceptions import NoMatch
 from .exceptions import RequestAliasRedirect
diff --git a/src/werkzeug/routing/matcher.py b/src/werkzeug/routing/matcher.py
--- a/src/werkzeug/routing/matcher.py
+++ b/src/werkzeug/routing/matcher.py
@@ -129,6 +129,22 @@
                     rv = _match(new_state, remaining, values + list(match.groups()))
                     if rv is not None:
                         return rv
+
+            # If there is no match and the only part left is a
+            # trailing slash ("") consider rules that aren't
+            # strict-slashes as these should match if there is a final
+            # slash part.
+            if parts == [""]:
+                for rule in state.rules:
+                    if rule.strict_slashes:
+                        continue
+                    if rule.methods is not None and method not in rule.methods:
+                        have_match_for.update(rule.methods)
+                    elif rule.websocket != websocket:
+                        websocket_mismatch = True
+                    else:
+                        return rule, values
+
             return None
 
         try:

{"golden_diff": "diff --git a/src/werkzeug/routing/__init__.py b/src/werkzeug/routing/__init__.py\n--- a/src/werkzeug/routing/__init__.py\n+++ b/src/werkzeug/routing/__init__.py\n@@ -112,6 +112,7 @@\n from .converters import PathConverter\n from .converters import UnicodeConverter\n from .converters import UUIDConverter\n+from .converters import ValidationError\n from .exceptions import BuildError\n from .exceptions import NoMatch\n from .exceptions import RequestAliasRedirect\ndiff --git a/src/werkzeug/routing/matcher.py b/src/werkzeug/routing/matcher.py\n--- a/src/werkzeug/routing/matcher.py\n+++ b/src/werkzeug/routing/matcher.py\n@@ -129,6 +129,22 @@\n                     rv = _match(new_state, remaining, values + list(match.groups()))\n                     if rv is not None:\n                         return rv\n+\n+            # If there is no match and the only part left is a\n+            # trailing slash (\"\") consider rules that aren't\n+            # strict-slashes as these should match if there is a final\n+            # slash part.\n+            if parts == [\"\"]:\n+                for rule in state.rules:\n+                    if rule.strict_slashes:\n+                        continue\n+                    if rule.methods is not None and method not in rule.methods:\n+                        have_match_for.update(rule.methods)\n+                    elif rule.websocket != websocket:\n+                        websocket_mismatch = True\n+                    else:\n+                        return rule, values\n+\n             return None\n \n         try:\n", "issue": "2.2.0 breaks werkzeug.routing.ValidationError import\n```\r\n(venv-test) $ pip install werkzeug\r\nCollecting werkzeug\r\n  Downloading Werkzeug-2.2.0-py3-none-any.whl (232 kB)\r\n     \u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501 232.2/232.2 KB 3.5 MB/s eta 0:00:00\r\nCollecting MarkupSafe>=2.1.1\r\n  Using cached MarkupSafe-2.1.1-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (25 kB)\r\nInstalling collected packages: MarkupSafe, werkzeug\r\nSuccessfully installed MarkupSafe-2.1.1 werkzeug-2.2.0\r\n(venv-test) $ python\r\nPython 3.10.4 (main, Jun 29 2022, 12:14:53) [GCC 11.2.0] on linux\r\nType \"help\", \"copyright\", \"credits\" or \"license\" for more information.\r\n>>> from werkzeug.routing import ValidationError\r\nTraceback (most recent call last):\r\n  File \"<stdin>\", line 1, in <module>\r\nImportError: cannot import name 'ValidationError' from 'werkzeug.routing' (/tmp/venv-test/lib/python3.10/site-packages/werkzeug/routing/__init__.py)\r\n```\r\n\r\nThis is a documented API for 2.2, e.g. https://werkzeug.palletsprojects.com/en/2.2.x/routing/#custom-converters example code.\r\n\r\nEnvironment:\r\n\r\n- Python version: 3.10\r\n- Werkzeug version: 2.2.0\r\n\n", "before_files": [{"content": "\"\"\"When it comes to combining multiple controller or view functions\n(however you want to call them) you need a dispatcher. A simple way\nwould be applying regular expression tests on the ``PATH_INFO`` and\ncalling registered callback functions that return the value then.\n\nThis module implements a much more powerful system than simple regular\nexpression matching because it can also convert values in the URLs and\nbuild URLs.\n\nHere a simple example that creates a URL map for an application with\ntwo subdomains (www and kb) and some URL rules:\n\n.. code-block:: python\n\n    m = Map([\n        # Static URLs\n        Rule('/', endpoint='static/index'),\n        Rule('/about', endpoint='static/about'),\n        Rule('/help', endpoint='static/help'),\n        # Knowledge Base\n        Subdomain('kb', [\n            Rule('/', endpoint='kb/index'),\n            Rule('/browse/', endpoint='kb/browse'),\n            Rule('/browse/<int:id>/', endpoint='kb/browse'),\n            Rule('/browse/<int:id>/<int:page>', endpoint='kb/browse')\n        ])\n    ], default_subdomain='www')\n\nIf the application doesn't use subdomains it's perfectly fine to not set\nthe default subdomain and not use the `Subdomain` rule factory. The\nendpoint in the rules can be anything, for example import paths or\nunique identifiers. The WSGI application can use those endpoints to get the\nhandler for that URL.  It doesn't have to be a string at all but it's\nrecommended.\n\nNow it's possible to create a URL adapter for one of the subdomains and\nbuild URLs:\n\n.. code-block:: python\n\n    c = m.bind('example.com')\n\n    c.build(\"kb/browse\", dict(id=42))\n    'http://kb.example.com/browse/42/'\n\n    c.build(\"kb/browse\", dict())\n    'http://kb.example.com/browse/'\n\n    c.build(\"kb/browse\", dict(id=42, page=3))\n    'http://kb.example.com/browse/42/3'\n\n    c.build(\"static/about\")\n    '/about'\n\n    c.build(\"static/index\", force_external=True)\n    'http://www.example.com/'\n\n    c = m.bind('example.com', subdomain='kb')\n\n    c.build(\"static/about\")\n    'http://www.example.com/about'\n\nThe first argument to bind is the server name *without* the subdomain.\nPer default it will assume that the script is mounted on the root, but\noften that's not the case so you can provide the real mount point as\nsecond argument:\n\n.. code-block:: python\n\n    c = m.bind('example.com', '/applications/example')\n\nThe third argument can be the subdomain, if not given the default\nsubdomain is used.  For more details about binding have a look at the\ndocumentation of the `MapAdapter`.\n\nAnd here is how you can match URLs:\n\n.. code-block:: python\n\n    c = m.bind('example.com')\n\n    c.match(\"/\")\n    ('static/index', {})\n\n    c.match(\"/about\")\n    ('static/about', {})\n\n    c = m.bind('example.com', '/', 'kb')\n\n    c.match(\"/\")\n    ('kb/index', {})\n\n    c.match(\"/browse/42/23\")\n    ('kb/browse', {'id': 42, 'page': 23})\n\nIf matching fails you get a ``NotFound`` exception, if the rule thinks\nit's a good idea to redirect (for example because the URL was defined\nto have a slash at the end but the request was missing that slash) it\nwill raise a ``RequestRedirect`` exception. Both are subclasses of\n``HTTPException`` so you can use those errors as responses in the\napplication.\n\nIf matching succeeded but the URL rule was incompatible to the given\nmethod (for example there were only rules for ``GET`` and ``HEAD`` but\nrouting tried to match a ``POST`` request) a ``MethodNotAllowed``\nexception is raised.\n\"\"\"\nfrom .converters import AnyConverter\nfrom .converters import BaseConverter\nfrom .converters import FloatConverter\nfrom .converters import IntegerConverter\nfrom .converters import PathConverter\nfrom .converters import UnicodeConverter\nfrom .converters import UUIDConverter\nfrom .exceptions import BuildError\nfrom .exceptions import NoMatch\nfrom .exceptions import RequestAliasRedirect\nfrom .exceptions import RequestPath\nfrom .exceptions import RequestRedirect\nfrom .exceptions import RoutingException\nfrom .exceptions import WebsocketMismatch\nfrom .map import Map\nfrom .map import MapAdapter\nfrom .matcher import StateMachineMatcher\nfrom .rules import EndpointPrefix\nfrom .rules import parse_converter_args\nfrom .rules import Rule\nfrom .rules import RuleFactory\nfrom .rules import RuleTemplate\nfrom .rules import RuleTemplateFactory\nfrom .rules import Subdomain\nfrom .rules import Submount\n", "path": "src/werkzeug/routing/__init__.py"}, {"content": "import re\nimport typing as t\nfrom dataclasses import dataclass\nfrom dataclasses import field\n\nfrom .converters import ValidationError\nfrom .exceptions import NoMatch\nfrom .exceptions import RequestAliasRedirect\nfrom .exceptions import RequestPath\nfrom .rules import Rule\nfrom .rules import RulePart\n\n\nclass SlashRequired(Exception):\n    pass\n\n\n@dataclass\nclass State:\n    \"\"\"A representation of a rule state.\n\n    This includes the *rules* that correspond to the state and the\n    possible *static* and *dynamic* transitions to the next state.\n    \"\"\"\n\n    dynamic: t.List[t.Tuple[RulePart, \"State\"]] = field(default_factory=list)\n    rules: t.List[Rule] = field(default_factory=list)\n    static: t.Dict[str, \"State\"] = field(default_factory=dict)\n\n\nclass StateMachineMatcher:\n    def __init__(self, merge_slashes: bool) -> None:\n        self._root = State()\n        self.merge_slashes = merge_slashes\n\n    def add(self, rule: Rule) -> None:\n        state = self._root\n        for part in rule._parts:\n            if part.static:\n                state.static.setdefault(part.content, State())\n                state = state.static[part.content]\n            else:\n                for test_part, new_state in state.dynamic:\n                    if test_part == part:\n                        state = new_state\n                        break\n                else:\n                    new_state = State()\n                    state.dynamic.append((part, new_state))\n                    state = new_state\n        state.rules.append(rule)\n\n    def update(self) -> None:\n        # For every state the dynamic transitions should be sorted by\n        # the weight of the transition\n        state = self._root\n\n        def _update_state(state: State) -> None:\n            state.dynamic.sort(key=lambda entry: entry[0].weight)\n            for new_state in state.static.values():\n                _update_state(new_state)\n            for _, new_state in state.dynamic:\n                _update_state(new_state)\n\n        _update_state(state)\n\n    def match(\n        self, domain: str, path: str, method: str, websocket: bool\n    ) -> t.Tuple[Rule, t.MutableMapping[str, t.Any]]:\n        # To match to a rule we need to start at the root state and\n        # try to follow the transitions until we find a match, or find\n        # there is no transition to follow.\n\n        have_match_for = set()\n        websocket_mismatch = False\n\n        def _match(\n            state: State, parts: t.List[str], values: t.List[str]\n        ) -> t.Optional[t.Tuple[Rule, t.List[str]]]:\n            # This function is meant to be called recursively, and will attempt\n            # to match the head part to the state's transitions.\n            nonlocal have_match_for, websocket_mismatch\n\n            # The base case is when all parts have been matched via\n            # transitions. Hence if there is a rule with methods &\n            # websocket that work return it and the dynamic values\n            # extracted.\n            if parts == []:\n                for rule in state.rules:\n                    if rule.methods is not None and method not in rule.methods:\n                        have_match_for.update(rule.methods)\n                    elif rule.websocket != websocket:\n                        websocket_mismatch = True\n                    else:\n                        return rule, values\n\n                # Test if there is a match with this path with a\n                # trailing slash, if so raise an exception to report\n                # that matching is possible with an additional slash\n                if \"\" in state.static:\n                    for rule in state.static[\"\"].rules:\n                        if (\n                            rule.strict_slashes\n                            and websocket == rule.websocket\n                            and (rule.methods is None or method in rule.methods)\n                        ):\n                            raise SlashRequired()\n                return None\n\n            part = parts[0]\n            # To match this part try the static transitions first\n            if part in state.static:\n                rv = _match(state.static[part], parts[1:], values)\n                if rv is not None:\n                    return rv\n            # No match via the static transitions, so try the dynamic\n            # ones.\n            for test_part, new_state in state.dynamic:\n                target = part\n                remaining = parts[1:]\n                # A final part indicates a transition that always\n                # consumes the remaining parts i.e. transitions to a\n                # final state.\n                if test_part.final:\n                    target = \"/\".join(parts)\n                    remaining = []\n                match = re.compile(test_part.content).match(target)\n                if match is not None:\n                    rv = _match(new_state, remaining, values + list(match.groups()))\n                    if rv is not None:\n                        return rv\n            return None\n\n        try:\n            rv = _match(self._root, [domain, *path.split(\"/\")], [])\n        except SlashRequired:\n            raise RequestPath(f\"{path}/\") from None\n\n        if self.merge_slashes and rv is None:\n            # Try to match again, but with slashes merged\n            path = re.sub(\"/{2,}?\", \"/\", path)\n            try:\n                rv = _match(self._root, [domain, *path.split(\"/\")], [])\n            except SlashRequired:\n                raise RequestPath(f\"{path}/\") from None\n            if rv is None:\n                raise NoMatch(have_match_for, websocket_mismatch)\n            else:\n                raise RequestPath(f\"{path}\")\n        elif rv is not None:\n            rule, values = rv\n\n            result = {}\n            for name, value in zip(rule._converters.keys(), values):\n                try:\n                    value = rule._converters[name].to_python(value)\n                except ValidationError:\n                    raise NoMatch(have_match_for, websocket_mismatch) from None\n                result[str(name)] = value\n            if rule.defaults:\n                result.update(rule.defaults)\n\n            if rule.alias and rule.map.redirect_defaults:\n                raise RequestAliasRedirect(result, rule.endpoint)\n\n            return rule, result\n\n        raise NoMatch(have_match_for, websocket_mismatch)\n", "path": "src/werkzeug/routing/matcher.py"}], "after_files": [{"content": "\"\"\"When it comes to combining multiple controller or view functions\n(however you want to call them) you need a dispatcher. A simple way\nwould be applying regular expression tests on the ``PATH_INFO`` and\ncalling registered callback functions that return the value then.\n\nThis module implements a much more powerful system than simple regular\nexpression matching because it can also convert values in the URLs and\nbuild URLs.\n\nHere a simple example that creates a URL map for an application with\ntwo subdomains (www and kb) and some URL rules:\n\n.. code-block:: python\n\n    m = Map([\n        # Static URLs\n        Rule('/', endpoint='static/index'),\n        Rule('/about', endpoint='static/about'),\n        Rule('/help', endpoint='static/help'),\n        # Knowledge Base\n        Subdomain('kb', [\n            Rule('/', endpoint='kb/index'),\n            Rule('/browse/', endpoint='kb/browse'),\n            Rule('/browse/<int:id>/', endpoint='kb/browse'),\n            Rule('/browse/<int:id>/<int:page>', endpoint='kb/browse')\n        ])\n    ], default_subdomain='www')\n\nIf the application doesn't use subdomains it's perfectly fine to not set\nthe default subdomain and not use the `Subdomain` rule factory. The\nendpoint in the rules can be anything, for example import paths or\nunique identifiers. The WSGI application can use those endpoints to get the\nhandler for that URL.  It doesn't have to be a string at all but it's\nrecommended.\n\nNow it's possible to create a URL adapter for one of the subdomains and\nbuild URLs:\n\n.. code-block:: python\n\n    c = m.bind('example.com')\n\n    c.build(\"kb/browse\", dict(id=42))\n    'http://kb.example.com/browse/42/'\n\n    c.build(\"kb/browse\", dict())\n    'http://kb.example.com/browse/'\n\n    c.build(\"kb/browse\", dict(id=42, page=3))\n    'http://kb.example.com/browse/42/3'\n\n    c.build(\"static/about\")\n    '/about'\n\n    c.build(\"static/index\", force_external=True)\n    'http://www.example.com/'\n\n    c = m.bind('example.com', subdomain='kb')\n\n    c.build(\"static/about\")\n    'http://www.example.com/about'\n\nThe first argument to bind is the server name *without* the subdomain.\nPer default it will assume that the script is mounted on the root, but\noften that's not the case so you can provide the real mount point as\nsecond argument:\n\n.. code-block:: python\n\n    c = m.bind('example.com', '/applications/example')\n\nThe third argument can be the subdomain, if not given the default\nsubdomain is used.  For more details about binding have a look at the\ndocumentation of the `MapAdapter`.\n\nAnd here is how you can match URLs:\n\n.. code-block:: python\n\n    c = m.bind('example.com')\n\n    c.match(\"/\")\n    ('static/index', {})\n\n    c.match(\"/about\")\n    ('static/about', {})\n\n    c = m.bind('example.com', '/', 'kb')\n\n    c.match(\"/\")\n    ('kb/index', {})\n\n    c.match(\"/browse/42/23\")\n    ('kb/browse', {'id': 42, 'page': 23})\n\nIf matching fails you get a ``NotFound`` exception, if the rule thinks\nit's a good idea to redirect (for example because the URL was defined\nto have a slash at the end but the request was missing that slash) it\nwill raise a ``RequestRedirect`` exception. Both are subclasses of\n``HTTPException`` so you can use those errors as responses in the\napplication.\n\nIf matching succeeded but the URL rule was incompatible to the given\nmethod (for example there were only rules for ``GET`` and ``HEAD`` but\nrouting tried to match a ``POST`` request) a ``MethodNotAllowed``\nexception is raised.\n\"\"\"\nfrom .converters import AnyConverter\nfrom .converters import BaseConverter\nfrom .converters import FloatConverter\nfrom .converters import IntegerConverter\nfrom .converters import PathConverter\nfrom .converters import UnicodeConverter\nfrom .converters import UUIDConverter\nfrom .converters import ValidationError\nfrom .exceptions import BuildError\nfrom .exceptions import NoMatch\nfrom .exceptions import RequestAliasRedirect\nfrom .exceptions import RequestPath\nfrom .exceptions import RequestRedirect\nfrom .exceptions import RoutingException\nfrom .exceptions import WebsocketMismatch\nfrom .map import Map\nfrom .map import MapAdapter\nfrom .matcher import StateMachineMatcher\nfrom .rules import EndpointPrefix\nfrom .rules import parse_converter_args\nfrom .rules import Rule\nfrom .rules import RuleFactory\nfrom .rules import RuleTemplate\nfrom .rules import RuleTemplateFactory\nfrom .rules import Subdomain\nfrom .rules import Submount\n", "path": "src/werkzeug/routing/__init__.py"}, {"content": "import re\nimport typing as t\nfrom dataclasses import dataclass\nfrom dataclasses import field\n\nfrom .converters import ValidationError\nfrom .exceptions import NoMatch\nfrom .exceptions import RequestAliasRedirect\nfrom .exceptions import RequestPath\nfrom .rules import Rule\nfrom .rules import RulePart\n\n\nclass SlashRequired(Exception):\n    pass\n\n\n@dataclass\nclass State:\n    \"\"\"A representation of a rule state.\n\n    This includes the *rules* that correspond to the state and the\n    possible *static* and *dynamic* transitions to the next state.\n    \"\"\"\n\n    dynamic: t.List[t.Tuple[RulePart, \"State\"]] = field(default_factory=list)\n    rules: t.List[Rule] = field(default_factory=list)\n    static: t.Dict[str, \"State\"] = field(default_factory=dict)\n\n\nclass StateMachineMatcher:\n    def __init__(self, merge_slashes: bool) -> None:\n        self._root = State()\n        self.merge_slashes = merge_slashes\n\n    def add(self, rule: Rule) -> None:\n        state = self._root\n        for part in rule._parts:\n            if part.static:\n                state.static.setdefault(part.content, State())\n                state = state.static[part.content]\n            else:\n                for test_part, new_state in state.dynamic:\n                    if test_part == part:\n                        state = new_state\n                        break\n                else:\n                    new_state = State()\n                    state.dynamic.append((part, new_state))\n                    state = new_state\n        state.rules.append(rule)\n\n    def update(self) -> None:\n        # For every state the dynamic transitions should be sorted by\n        # the weight of the transition\n        state = self._root\n\n        def _update_state(state: State) -> None:\n            state.dynamic.sort(key=lambda entry: entry[0].weight)\n            for new_state in state.static.values():\n                _update_state(new_state)\n            for _, new_state in state.dynamic:\n                _update_state(new_state)\n\n        _update_state(state)\n\n    def match(\n        self, domain: str, path: str, method: str, websocket: bool\n    ) -> t.Tuple[Rule, t.MutableMapping[str, t.Any]]:\n        # To match to a rule we need to start at the root state and\n        # try to follow the transitions until we find a match, or find\n        # there is no transition to follow.\n\n        have_match_for = set()\n        websocket_mismatch = False\n\n        def _match(\n            state: State, parts: t.List[str], values: t.List[str]\n        ) -> t.Optional[t.Tuple[Rule, t.List[str]]]:\n            # This function is meant to be called recursively, and will attempt\n            # to match the head part to the state's transitions.\n            nonlocal have_match_for, websocket_mismatch\n\n            # The base case is when all parts have been matched via\n            # transitions. Hence if there is a rule with methods &\n            # websocket that work return it and the dynamic values\n            # extracted.\n            if parts == []:\n                for rule in state.rules:\n                    if rule.methods is not None and method not in rule.methods:\n                        have_match_for.update(rule.methods)\n                    elif rule.websocket != websocket:\n                        websocket_mismatch = True\n                    else:\n                        return rule, values\n\n                # Test if there is a match with this path with a\n                # trailing slash, if so raise an exception to report\n                # that matching is possible with an additional slash\n                if \"\" in state.static:\n                    for rule in state.static[\"\"].rules:\n                        if (\n                            rule.strict_slashes\n                            and websocket == rule.websocket\n                            and (rule.methods is None or method in rule.methods)\n                        ):\n                            raise SlashRequired()\n                return None\n\n            part = parts[0]\n            # To match this part try the static transitions first\n            if part in state.static:\n                rv = _match(state.static[part], parts[1:], values)\n                if rv is not None:\n                    return rv\n            # No match via the static transitions, so try the dynamic\n            # ones.\n            for test_part, new_state in state.dynamic:\n                target = part\n                remaining = parts[1:]\n                # A final part indicates a transition that always\n                # consumes the remaining parts i.e. transitions to a\n                # final state.\n                if test_part.final:\n                    target = \"/\".join(parts)\n                    remaining = []\n                match = re.compile(test_part.content).match(target)\n                if match is not None:\n                    rv = _match(new_state, remaining, values + list(match.groups()))\n                    if rv is not None:\n                        return rv\n\n            # If there is no match and the only part left is a\n            # trailing slash (\"\") consider rules that aren't\n            # strict-slashes as these should match if there is a final\n            # slash part.\n            if parts == [\"\"]:\n                for rule in state.rules:\n                    if rule.strict_slashes:\n                        continue\n                    if rule.methods is not None and method not in rule.methods:\n                        have_match_for.update(rule.methods)\n                    elif rule.websocket != websocket:\n                        websocket_mismatch = True\n                    else:\n                        return rule, values\n\n            return None\n\n        try:\n            rv = _match(self._root, [domain, *path.split(\"/\")], [])\n        except SlashRequired:\n            raise RequestPath(f\"{path}/\") from None\n\n        if self.merge_slashes and rv is None:\n            # Try to match again, but with slashes merged\n            path = re.sub(\"/{2,}?\", \"/\", path)\n            try:\n                rv = _match(self._root, [domain, *path.split(\"/\")], [])\n            except SlashRequired:\n                raise RequestPath(f\"{path}/\") from None\n            if rv is None:\n                raise NoMatch(have_match_for, websocket_mismatch)\n            else:\n                raise RequestPath(f\"{path}\")\n        elif rv is not None:\n            rule, values = rv\n\n            result = {}\n            for name, value in zip(rule._converters.keys(), values):\n                try:\n                    value = rule._converters[name].to_python(value)\n                except ValidationError:\n                    raise NoMatch(have_match_for, websocket_mismatch) from None\n                result[str(name)] = value\n            if rule.defaults:\n                result.update(rule.defaults)\n\n            if rule.alias and rule.map.redirect_defaults:\n                raise RequestAliasRedirect(result, rule.endpoint)\n\n            return rule, result\n\n        raise NoMatch(have_match_for, websocket_mismatch)\n", "path": "src/werkzeug/routing/matcher.py"}]}