We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
Path segment in one route's URI template masks the field expression in another route
The following test demonstrates the issue. The assertion fails since the resulting status code is 404, rather than 200. "/v2.0/thing" should route to `/{version}/thing` instead of `/v2.0`.

``` py
def test_string_vs_var(self):
    self.api.add_route('/v2.0', self.resource)
    self.simulate_request('/v2.0')

    self.api.add_route('/{version}/thing', testing.TestResource())
    self.simulate_request('/v2.0/thing')
    self.assertEqual(self.srmock.status, falcon.HTTP_200)
```

```
/{version}/foo/bar
/v1.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: `falcon/routing/compiled.py`
Content:
```
1 # Copyright 2013 by Richard Olsson
2 #
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
6 #
7 #    http://www.apache.org/licenses/LICENSE-2.0
8 #
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
14 
15 import re
16 
17 
18 TAB_STR = ' ' * 4
19 
20 
21 class CompiledRouter(object):
22     """Fast URI router which compiles its routing logic to Python code.
23 
24     Generally you do not need to use this router class directly, as an
25     instance is created by default when the falcon.API class is initialized.
26 
27     The router treats URI paths as a tree of URI segments and searches by
28     checking the URI one segment at a time. Instead of interpreting the route
29     tree for each look-up, it generates inlined, bespoke Python code to
30     perform the search, then compiles that code. This makes the route
31     processing quite fast.
32     """
33 
34     def __init__(self):
35         self._roots = []
36         self._find = self._compile()
37         self._code_lines = None
38         self._src = None
39         self._expressions = None
40         self._return_values = None
41 
42     def add_route(self, uri_template, method_map, resource):
43         """Adds a route between URI path template and resource."""
44         # Can't start with a number, since these eventually get passed as
45         # args to on_* responders
46         if re.search('{\d', uri_template):
47             raise ValueError('Field names may not start with a digit.')
48 
49         if re.search('\s', uri_template):
50             raise ValueError('URI templates may not include whitespace.')
51 
52         path = uri_template.strip('/').split('/')
53 
54         def insert(nodes, path_index=0):
55             for node in nodes:
56                 segment = path[path_index]
57                 if node.matches(segment):
58                     path_index += 1
59                     if path_index == len(path):
60                         # NOTE(kgriffs): Override previous node
61                         node.method_map = method_map
62                         node.resource = resource
63                     else:
64                         insert(node.children, path_index)
65 
66                     return
67 
68                 if node.conflicts_with(segment):
69                     raise ValueError('The URI template for this route '
70                                      "conflicts with another route's "
71                                      'template.')
72 
73             # NOTE(richardolsson): If we got this far, the node doesn't already
74             # exist and needs to be created. This builds a new branch of the
75             # routing tree recursively until it reaches the new node leaf.
76             new_node = CompiledRouterNode(path[path_index])
77             nodes.append(new_node)
78             if path_index == len(path) - 1:
79                 new_node.method_map = method_map
80                 new_node.resource = resource
81             else:
82                 insert(new_node.children, path_index + 1)
83 
84         insert(self._roots)
85         self._find = self._compile()
86 
87     def find(self, uri):
88         """Finds resource and method map for a URI, or returns None."""
89         path = uri.lstrip('/').split('/')
90         params = {}
91         node = self._find(path, self._return_values, self._expressions, params)
92 
93         if node is not None:
94             return node.resource, node.method_map, params
95         else:
96             return None, None, None
97 
98     def _compile_tree(self, nodes, indent=1, level=0):
99         """Generates Python code for a routing tree or subtree."""
100 
101         def line(text, indent_offset=0):
102             pad = TAB_STR * (indent + indent_offset)
103             self._code_lines.append(pad + text)
104 
105         # NOTE(kgriffs): Base case
106         if not nodes:
107             return
108 
109         line('if path_len > %d:' % level)
110         indent += 1
111 
112         level_indent = indent
113         found_simple = False
114 
115         # NOTE(kgriffs & philiptzou): Sort nodes in this sequence:
116         # static nodes(0), complex var nodes(1) and simple var nodes(2).
117         # so that none of them get masked.
118         nodes = sorted(
119             nodes, key=lambda node: node.is_var + (node.is_var and
120                                                    not node.is_complex))
121 
122         for node in nodes:
123             if node.is_var:
124                 if node.is_complex:
125                     # NOTE(richardolsson): Complex nodes are nodes which
126                     # contain anything more than a single literal or variable,
127                     # and they need to be checked using a pre-compiled regular
128                     # expression.
129                     expression_idx = len(self._expressions)
130                     self._expressions.append(node.var_regex)
131 
132                     line('match = expressions[%d].match(path[%d]) # %s' % (
133                         expression_idx, level, node.var_regex.pattern))
134 
135                     line('if match is not None:')
136                     indent += 1
137                     line('params.update(match.groupdict())')
138 
139                 else:
140                     # NOTE(kgriffs): Simple nodes just capture the entire path
141                     # segment as the value for the param.
142                     line('params["%s"] = path[%d]' % (node.var_name, level))
143 
144                     # NOTE(kgriffs): We don't allow multiple simple var nodes
145                     # to exist at the same level, e.g.:
146                     #
147                     #   /foo/{id}/bar
148                     #   /foo/{name}/bar
149                     #
150                     assert len([_node for _node in nodes
151                                 if _node.is_var and not _node.is_complex]) == 1
152                     found_simple = True
153 
154             else:
155                 # NOTE(kgriffs): Not a param, so must match exactly
156                 line('if path[%d] == "%s":' % (level, node.raw_segment))
157                 indent += 1
158 
159             if node.resource is not None:
160                 # NOTE(kgriffs): This is a valid route, so we will want to
161                 # return the relevant information.
162                 resource_idx = len(self._return_values)
163                 self._return_values.append(node)
164 
165             self._compile_tree(node.children, indent, level + 1)
166 
167             if node.resource is None:
168                 line('return None')
169             else:
170                 # NOTE(kgriffs): Make sure that we have consumed all of
171                 # the segments for the requested route; otherwise we could
172                 # mistakenly match "/foo/23/bar" against "/foo/{id}".
173                 line('if path_len == %d:' % (level + 1))
174                 line('return return_values[%d]' % resource_idx, 1)
175 
176                 line('return None')
177 
178             indent = level_indent
179 
180         if not found_simple:
181             line('return None')
182 
183     def _compile(self):
184         """Generates Python code for entire routing tree.
185 
186         The generated code is compiled and the resulting Python method is
187         returned.
188         """
189         self._return_values = []
190         self._expressions = []
191         self._code_lines = [
192             'def find(path, return_values, expressions, params):',
193             TAB_STR + 'path_len = len(path)',
194         ]
195 
196         self._compile_tree(self._roots)
197 
198         self._code_lines.append(
199             # PERF(kgriffs): Explicit return of None is faster than implicit
200             TAB_STR + 'return None'
201         )
202 
203         self._src = '\n'.join(self._code_lines)
204 
205         scope = {}
206         exec(compile(self._src, '<string>', 'exec'), scope)
207 
208         return scope['find']
209 
210 
211 class CompiledRouterNode(object):
212     """Represents a single URI segment in a URI."""
213 
214     _regex_vars = re.compile('{([-_a-zA-Z0-9]+)}')
215 
216     def __init__(self, raw_segment, method_map=None, resource=None):
217         self.children = []
218 
219         self.raw_segment = raw_segment
220         self.method_map = method_map
221         self.resource = resource
222 
223         self.is_var = False
224         self.is_complex = False
225         self.var_name = None
226 
227         seg = raw_segment.replace('.', '\\.')
228 
229         matches = list(self._regex_vars.finditer(seg))
230         if matches:
231             self.is_var = True
232             # NOTE(richardolsson): if there is a single variable and it spans
233             # the entire segment, the segment is uncomplex and the variable
234             # name is simply the string contained within curly braces.
235             if len(matches) == 1 and matches[0].span() == (0, len(seg)):
236                 self.is_complex = False
237                 self.var_name = raw_segment[1:-1]
238             else:
239                 # NOTE(richardolsson): Complex segments need to be converted
240                 # into regular expressions will be used to match and extract
241                 # variable values. The regular expressions contain both
242                 # literal spans and named group expressions for the variables.
243                 self.is_complex = True
244                 seg_fields = []
245                 prev_end_idx = 0
246                 for match in matches:
247                     var_start_idx, var_end_idx = match.span()
248                     seg_fields.append(seg[prev_end_idx:var_start_idx])
249 
250                     var_name = match.groups()[0].replace('-', '_')
251                     seg_fields.append('(?P<%s>[^/]+)' % var_name)
252 
253                     prev_end_idx = var_end_idx
254 
255                 seg_fields.append(seg[prev_end_idx:])
256                 seg_pattern = ''.join(seg_fields)
257                 self.var_regex = re.compile(seg_pattern)
258         else:
259             self.is_var = False
260 
261     def matches(self, segment):
262         """Returns True if this node matches the supplied template segment."""
263 
264         return segment == self.raw_segment
265 
266     def conflicts_with(self, segment):
267         """Returns True if this node conflicts with a given template segment."""
268 
269         # NOTE(kgriffs): This method assumes that the caller has already
270         # checked if the segment matches. By definition, only unmatched
271         # segments may conflict, so there isn't any sense in calling
272         # conflicts_with in that case.
273         assert not self.matches(segment)
274 
275         # NOTE(kgriffs): Possible combinations are as follows.
276         #
277         #   simple, simple ==> True
278         #   simple, complex ==> False
279         #   simple, string ==> False
280         #   complex, simple ==> False
281         #   complex, complex ==> (Depend)
282         #   complex, string ==> False
283         #   string, simple ==> False
284         #   string, complex ==> False
285         #   string, string ==> False
286         #
287         other = CompiledRouterNode(segment)
288 
289         if self.is_var:
290             # NOTE(kgriffs & philiptzou): Falcon does not accept multiple
291             # simple var nodes exist at the same level as following:
292             #
293             #   /foo/{thing1}
294             #   /foo/{thing2}
295             #
296             # Nor two complex nodes like this:
297             #
298             #   /foo/{thing1}.{ext}
299             #   /foo/{thing2}.{ext}
300             #
301             # On the other hand, those are all OK:
302             #
303             #   /foo/{thing1}
304             #   /foo/all
305             #   /foo/{thing1}.{ext}
306             #   /foo/{thing2}.detail.{ext}
307             #
308             if self.is_complex:
309                 if other.is_complex:
310                     return (self._regex_vars.sub('v', self.raw_segment) ==
311                             self._regex_vars.sub('v', segment))
312 
313                 return False
314             else:
315                 return other.is_var and not other.is_complex
316 
317         # NOTE(kgriffs): If self is a static string match, then all the cases
318         # for other are False, so no need to check.
319         return False
320
```
--- 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/falcon/routing/compiled.py b/falcon/routing/compiled.py
--- a/falcon/routing/compiled.py
+++ b/falcon/routing/compiled.py
@@ -95,7 +95,7 @@
         else:
             return None, None, None
 
-    def _compile_tree(self, nodes, indent=1, level=0):
+    def _compile_tree(self, nodes, indent=1, level=0, fast_return=True):
         """Generates Python code for a routing tree or subtree."""
 
         def line(text, indent_offset=0):
@@ -119,6 +119,18 @@
             nodes, key=lambda node: node.is_var + (node.is_var and
                                                    not node.is_complex))
 
+        # NOTE(kgriffs): Down to this branch in the tree, we can do a
+        # fast 'return None'. See if the nodes at this branch are
+        # all still simple, meaning there is only one possible path.
+        if fast_return:
+            if len(nodes) > 1:
+                # NOTE(kgriffs): There's the possibility of more than
+                # one path.
+                var_nodes = [node for node in nodes if node.is_var]
+                found_var_nodes = bool(var_nodes)
+
+                fast_return = not found_var_nodes
+
         for node in nodes:
             if node.is_var:
                 if node.is_complex:
@@ -162,10 +174,11 @@
                 resource_idx = len(self._return_values)
                 self._return_values.append(node)
 
-            self._compile_tree(node.children, indent, level + 1)
+            self._compile_tree(node.children, indent, level + 1, fast_return)
 
             if node.resource is None:
-                line('return None')
+                if fast_return:
+                    line('return None')
             else:
                 # NOTE(kgriffs): Make sure that we have consumed all of
                 # the segments for the requested route; otherwise we could
@@ -173,11 +186,12 @@
                 line('if path_len == %d:' % (level + 1))
                 line('return return_values[%d]' % resource_idx, 1)
 
-                line('return None')
+                if fast_return:
+                    line('return None')
 
             indent = level_indent
 
-        if not found_simple:
+        if not found_simple and fast_return:
             line('return None')
 
     def _compile(self):

{"golden_diff": "diff --git a/falcon/routing/compiled.py b/falcon/routing/compiled.py\n--- a/falcon/routing/compiled.py\n+++ b/falcon/routing/compiled.py\n@@ -95,7 +95,7 @@\n         else:\n             return None, None, None\n \n-    def _compile_tree(self, nodes, indent=1, level=0):\n+    def _compile_tree(self, nodes, indent=1, level=0, fast_return=True):\n         \"\"\"Generates Python code for a routing tree or subtree.\"\"\"\n \n         def line(text, indent_offset=0):\n@@ -119,6 +119,18 @@\n             nodes, key=lambda node: node.is_var + (node.is_var and\n                                                    not node.is_complex))\n \n+        # NOTE(kgriffs): Down to this branch in the tree, we can do a\n+        # fast 'return None'. See if the nodes at this branch are\n+        # all still simple, meaning there is only one possible path.\n+        if fast_return:\n+            if len(nodes) > 1:\n+                # NOTE(kgriffs): There's the possibility of more than\n+                # one path.\n+                var_nodes = [node for node in nodes if node.is_var]\n+                found_var_nodes = bool(var_nodes)\n+\n+                fast_return = not found_var_nodes\n+\n         for node in nodes:\n             if node.is_var:\n                 if node.is_complex:\n@@ -162,10 +174,11 @@\n                 resource_idx = len(self._return_values)\n                 self._return_values.append(node)\n \n-            self._compile_tree(node.children, indent, level + 1)\n+            self._compile_tree(node.children, indent, level + 1, fast_return)\n \n             if node.resource is None:\n-                line('return None')\n+                if fast_return:\n+                    line('return None')\n             else:\n                 # NOTE(kgriffs): Make sure that we have consumed all of\n                 # the segments for the requested route; otherwise we could\n@@ -173,11 +186,12 @@\n                 line('if path_len == %d:' % (level + 1))\n                 line('return return_values[%d]' % resource_idx, 1)\n \n-                line('return None')\n+                if fast_return:\n+                    line('return None')\n \n             indent = level_indent\n \n-        if not found_simple:\n+        if not found_simple and fast_return:\n             line('return None')\n \n     def _compile(self):\n", "issue": "Path segment in one route's URI template masks the field expression in another route\nThe following test demonstrates the issue. The assertion fails since the resulting status code is 404, rather than 200. \"/v2.0/thing\" should route to `/{version}/thing` instead of `/v2.0`.\n\n``` py\ndef test_string_vs_var(self):\n    self.api.add_route('/v2.0', self.resource)\n    self.simulate_request('/v2.0')\n\n    self.api.add_route('/{version}/thing', testing.TestResource())\n    self.simulate_request('/v2.0/thing')\n    self.assertEqual(self.srmock.status, falcon.HTTP_200)\n```\n\n```\n/{version}/foo/bar\n/v1.0\n```\n\n", "before_files": [{"content": "# Copyright 2013 by Richard Olsson\n#\n# Licensed under the Apache License, Version 2.0 (the \"License\");\n# you may not use this file except in compliance with the License.\n# You may obtain a copy of the License at\n#\n#    http://www.apache.org/licenses/LICENSE-2.0\n#\n# Unless required by applicable law or agreed to in writing, software\n# distributed under the License is distributed on an \"AS IS\" BASIS,\n# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n# See the License for the specific language governing permissions and\n# limitations under the License.\n\nimport re\n\n\nTAB_STR = ' ' * 4\n\n\nclass CompiledRouter(object):\n    \"\"\"Fast URI router which compiles its routing logic to Python code.\n\n    Generally you do not need to use this router class directly, as an\n    instance is created by default when the falcon.API class is initialized.\n\n    The router treats URI paths as a tree of URI segments and searches by\n    checking the URI one segment at a time. Instead of interpreting the route\n    tree for each look-up, it generates inlined, bespoke Python code to\n    perform the search, then compiles that code. This makes the route\n    processing quite fast.\n    \"\"\"\n\n    def __init__(self):\n        self._roots = []\n        self._find = self._compile()\n        self._code_lines = None\n        self._src = None\n        self._expressions = None\n        self._return_values = None\n\n    def add_route(self, uri_template, method_map, resource):\n        \"\"\"Adds a route between URI path template and resource.\"\"\"\n        # Can't start with a number, since these eventually get passed as\n        # args to on_* responders\n        if re.search('{\\d', uri_template):\n            raise ValueError('Field names may not start with a digit.')\n\n        if re.search('\\s', uri_template):\n            raise ValueError('URI templates may not include whitespace.')\n\n        path = uri_template.strip('/').split('/')\n\n        def insert(nodes, path_index=0):\n            for node in nodes:\n                segment = path[path_index]\n                if node.matches(segment):\n                    path_index += 1\n                    if path_index == len(path):\n                        # NOTE(kgriffs): Override previous node\n                        node.method_map = method_map\n                        node.resource = resource\n                    else:\n                        insert(node.children, path_index)\n\n                    return\n\n                if node.conflicts_with(segment):\n                    raise ValueError('The URI template for this route '\n                                     \"conflicts with another route's \"\n                                     'template.')\n\n            # NOTE(richardolsson): If we got this far, the node doesn't already\n            # exist and needs to be created. This builds a new branch of the\n            # routing tree recursively until it reaches the new node leaf.\n            new_node = CompiledRouterNode(path[path_index])\n            nodes.append(new_node)\n            if path_index == len(path) - 1:\n                new_node.method_map = method_map\n                new_node.resource = resource\n            else:\n                insert(new_node.children, path_index + 1)\n\n        insert(self._roots)\n        self._find = self._compile()\n\n    def find(self, uri):\n        \"\"\"Finds resource and method map for a URI, or returns None.\"\"\"\n        path = uri.lstrip('/').split('/')\n        params = {}\n        node = self._find(path, self._return_values, self._expressions, params)\n\n        if node is not None:\n            return node.resource, node.method_map, params\n        else:\n            return None, None, None\n\n    def _compile_tree(self, nodes, indent=1, level=0):\n        \"\"\"Generates Python code for a routing tree or subtree.\"\"\"\n\n        def line(text, indent_offset=0):\n            pad = TAB_STR * (indent + indent_offset)\n            self._code_lines.append(pad + text)\n\n        # NOTE(kgriffs): Base case\n        if not nodes:\n            return\n\n        line('if path_len > %d:' % level)\n        indent += 1\n\n        level_indent = indent\n        found_simple = False\n\n        # NOTE(kgriffs & philiptzou): Sort nodes in this sequence:\n        # static nodes(0), complex var nodes(1) and simple var nodes(2).\n        # so that none of them get masked.\n        nodes = sorted(\n            nodes, key=lambda node: node.is_var + (node.is_var and\n                                                   not node.is_complex))\n\n        for node in nodes:\n            if node.is_var:\n                if node.is_complex:\n                    # NOTE(richardolsson): Complex nodes are nodes which\n                    # contain anything more than a single literal or variable,\n                    # and they need to be checked using a pre-compiled regular\n                    # expression.\n                    expression_idx = len(self._expressions)\n                    self._expressions.append(node.var_regex)\n\n                    line('match = expressions[%d].match(path[%d]) # %s' % (\n                        expression_idx, level, node.var_regex.pattern))\n\n                    line('if match is not None:')\n                    indent += 1\n                    line('params.update(match.groupdict())')\n\n                else:\n                    # NOTE(kgriffs): Simple nodes just capture the entire path\n                    # segment as the value for the param.\n                    line('params[\"%s\"] = path[%d]' % (node.var_name, level))\n\n                    # NOTE(kgriffs): We don't allow multiple simple var nodes\n                    # to exist at the same level, e.g.:\n                    #\n                    #   /foo/{id}/bar\n                    #   /foo/{name}/bar\n                    #\n                    assert len([_node for _node in nodes\n                                if _node.is_var and not _node.is_complex]) == 1\n                    found_simple = True\n\n            else:\n                # NOTE(kgriffs): Not a param, so must match exactly\n                line('if path[%d] == \"%s\":' % (level, node.raw_segment))\n                indent += 1\n\n            if node.resource is not None:\n                # NOTE(kgriffs): This is a valid route, so we will want to\n                # return the relevant information.\n                resource_idx = len(self._return_values)\n                self._return_values.append(node)\n\n            self._compile_tree(node.children, indent, level + 1)\n\n            if node.resource is None:\n                line('return None')\n            else:\n                # NOTE(kgriffs): Make sure that we have consumed all of\n                # the segments for the requested route; otherwise we could\n                # mistakenly match \"/foo/23/bar\" against \"/foo/{id}\".\n                line('if path_len == %d:' % (level + 1))\n                line('return return_values[%d]' % resource_idx, 1)\n\n                line('return None')\n\n            indent = level_indent\n\n        if not found_simple:\n            line('return None')\n\n    def _compile(self):\n        \"\"\"Generates Python code for entire routing tree.\n\n        The generated code is compiled and the resulting Python method is\n        returned.\n        \"\"\"\n        self._return_values = []\n        self._expressions = []\n        self._code_lines = [\n            'def find(path, return_values, expressions, params):',\n            TAB_STR + 'path_len = len(path)',\n        ]\n\n        self._compile_tree(self._roots)\n\n        self._code_lines.append(\n            # PERF(kgriffs): Explicit return of None is faster than implicit\n            TAB_STR + 'return None'\n        )\n\n        self._src = '\\n'.join(self._code_lines)\n\n        scope = {}\n        exec(compile(self._src, '<string>', 'exec'), scope)\n\n        return scope['find']\n\n\nclass CompiledRouterNode(object):\n    \"\"\"Represents a single URI segment in a URI.\"\"\"\n\n    _regex_vars = re.compile('{([-_a-zA-Z0-9]+)}')\n\n    def __init__(self, raw_segment, method_map=None, resource=None):\n        self.children = []\n\n        self.raw_segment = raw_segment\n        self.method_map = method_map\n        self.resource = resource\n\n        self.is_var = False\n        self.is_complex = False\n        self.var_name = None\n\n        seg = raw_segment.replace('.', '\\\\.')\n\n        matches = list(self._regex_vars.finditer(seg))\n        if matches:\n            self.is_var = True\n            # NOTE(richardolsson): if there is a single variable and it spans\n            # the entire segment, the segment is uncomplex and the variable\n            # name is simply the string contained within curly braces.\n            if len(matches) == 1 and matches[0].span() == (0, len(seg)):\n                self.is_complex = False\n                self.var_name = raw_segment[1:-1]\n            else:\n                # NOTE(richardolsson): Complex segments need to be converted\n                # into regular expressions will be used to match and extract\n                # variable values. The regular expressions contain both\n                # literal spans and named group expressions for the variables.\n                self.is_complex = True\n                seg_fields = []\n                prev_end_idx = 0\n                for match in matches:\n                    var_start_idx, var_end_idx = match.span()\n                    seg_fields.append(seg[prev_end_idx:var_start_idx])\n\n                    var_name = match.groups()[0].replace('-', '_')\n                    seg_fields.append('(?P<%s>[^/]+)' % var_name)\n\n                    prev_end_idx = var_end_idx\n\n                seg_fields.append(seg[prev_end_idx:])\n                seg_pattern = ''.join(seg_fields)\n                self.var_regex = re.compile(seg_pattern)\n        else:\n            self.is_var = False\n\n    def matches(self, segment):\n        \"\"\"Returns True if this node matches the supplied template segment.\"\"\"\n\n        return segment == self.raw_segment\n\n    def conflicts_with(self, segment):\n        \"\"\"Returns True if this node conflicts with a given template segment.\"\"\"\n\n        # NOTE(kgriffs): This method assumes that the caller has already\n        # checked if the segment matches. By definition, only unmatched\n        # segments may conflict, so there isn't any sense in calling\n        # conflicts_with in that case.\n        assert not self.matches(segment)\n\n        # NOTE(kgriffs): Possible combinations are as follows.\n        #\n        #   simple, simple ==> True\n        #   simple, complex ==> False\n        #   simple, string ==> False\n        #   complex, simple ==> False\n        #   complex, complex ==> (Depend)\n        #   complex, string ==> False\n        #   string, simple ==> False\n        #   string, complex ==> False\n        #   string, string ==> False\n        #\n        other = CompiledRouterNode(segment)\n\n        if self.is_var:\n            # NOTE(kgriffs & philiptzou): Falcon does not accept multiple\n            # simple var nodes exist at the same level as following:\n            #\n            #   /foo/{thing1}\n            #   /foo/{thing2}\n            #\n            # Nor two complex nodes like this:\n            #\n            #   /foo/{thing1}.{ext}\n            #   /foo/{thing2}.{ext}\n            #\n            # On the other hand, those are all OK:\n            #\n            #   /foo/{thing1}\n            #   /foo/all\n            #   /foo/{thing1}.{ext}\n            #   /foo/{thing2}.detail.{ext}\n            #\n            if self.is_complex:\n                if other.is_complex:\n                    return (self._regex_vars.sub('v', self.raw_segment) ==\n                            self._regex_vars.sub('v', segment))\n\n                return False\n            else:\n                return other.is_var and not other.is_complex\n\n        # NOTE(kgriffs): If self is a static string match, then all the cases\n        # for other are False, so no need to check.\n        return False\n", "path": "falcon/routing/compiled.py"}], "after_files": [{"content": "# Copyright 2013 by Richard Olsson\n#\n# Licensed under the Apache License, Version 2.0 (the \"License\");\n# you may not use this file except in compliance with the License.\n# You may obtain a copy of the License at\n#\n#    http://www.apache.org/licenses/LICENSE-2.0\n#\n# Unless required by applicable law or agreed to in writing, software\n# distributed under the License is distributed on an \"AS IS\" BASIS,\n# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n# See the License for the specific language governing permissions and\n# limitations under the License.\n\nimport re\n\n\nTAB_STR = ' ' * 4\n\n\nclass CompiledRouter(object):\n    \"\"\"Fast URI router which compiles its routing logic to Python code.\n\n    Generally you do not need to use this router class directly, as an\n    instance is created by default when the falcon.API class is initialized.\n\n    The router treats URI paths as a tree of URI segments and searches by\n    checking the URI one segment at a time. Instead of interpreting the route\n    tree for each look-up, it generates inlined, bespoke Python code to\n    perform the search, then compiles that code. This makes the route\n    processing quite fast.\n    \"\"\"\n\n    def __init__(self):\n        self._roots = []\n        self._find = self._compile()\n        self._code_lines = None\n        self._src = None\n        self._expressions = None\n        self._return_values = None\n\n    def add_route(self, uri_template, method_map, resource):\n        \"\"\"Adds a route between URI path template and resource.\"\"\"\n        # Can't start with a number, since these eventually get passed as\n        # args to on_* responders\n        if re.search('{\\d', uri_template):\n            raise ValueError('Field names may not start with a digit.')\n\n        if re.search('\\s', uri_template):\n            raise ValueError('URI templates may not include whitespace.')\n\n        path = uri_template.strip('/').split('/')\n\n        def insert(nodes, path_index=0):\n            for node in nodes:\n                segment = path[path_index]\n                if node.matches(segment):\n                    path_index += 1\n                    if path_index == len(path):\n                        # NOTE(kgriffs): Override previous node\n                        node.method_map = method_map\n                        node.resource = resource\n                    else:\n                        insert(node.children, path_index)\n\n                    return\n\n                if node.conflicts_with(segment):\n                    raise ValueError('The URI template for this route '\n                                     \"conflicts with another route's \"\n                                     'template.')\n\n            # NOTE(richardolsson): If we got this far, the node doesn't already\n            # exist and needs to be created. This builds a new branch of the\n            # routing tree recursively until it reaches the new node leaf.\n            new_node = CompiledRouterNode(path[path_index])\n            nodes.append(new_node)\n            if path_index == len(path) - 1:\n                new_node.method_map = method_map\n                new_node.resource = resource\n            else:\n                insert(new_node.children, path_index + 1)\n\n        insert(self._roots)\n        self._find = self._compile()\n\n    def find(self, uri):\n        \"\"\"Finds resource and method map for a URI, or returns None.\"\"\"\n        path = uri.lstrip('/').split('/')\n        params = {}\n        node = self._find(path, self._return_values, self._expressions, params)\n\n        if node is not None:\n            return node.resource, node.method_map, params\n        else:\n            return None, None, None\n\n    def _compile_tree(self, nodes, indent=1, level=0, fast_return=True):\n        \"\"\"Generates Python code for a routing tree or subtree.\"\"\"\n\n        def line(text, indent_offset=0):\n            pad = TAB_STR * (indent + indent_offset)\n            self._code_lines.append(pad + text)\n\n        # NOTE(kgriffs): Base case\n        if not nodes:\n            return\n\n        line('if path_len > %d:' % level)\n        indent += 1\n\n        level_indent = indent\n        found_simple = False\n\n        # NOTE(kgriffs & philiptzou): Sort nodes in this sequence:\n        # static nodes(0), complex var nodes(1) and simple var nodes(2).\n        # so that none of them get masked.\n        nodes = sorted(\n            nodes, key=lambda node: node.is_var + (node.is_var and\n                                                   not node.is_complex))\n\n        # NOTE(kgriffs): Down to this branch in the tree, we can do a\n        # fast 'return None'. See if the nodes at this branch are\n        # all still simple, meaning there is only one possible path.\n        if fast_return:\n            if len(nodes) > 1:\n                # NOTE(kgriffs): There's the possibility of more than\n                # one path.\n                var_nodes = [node for node in nodes if node.is_var]\n                found_var_nodes = bool(var_nodes)\n\n                fast_return = not found_var_nodes\n\n        for node in nodes:\n            if node.is_var:\n                if node.is_complex:\n                    # NOTE(richardolsson): Complex nodes are nodes which\n                    # contain anything more than a single literal or variable,\n                    # and they need to be checked using a pre-compiled regular\n                    # expression.\n                    expression_idx = len(self._expressions)\n                    self._expressions.append(node.var_regex)\n\n                    line('match = expressions[%d].match(path[%d]) # %s' % (\n                        expression_idx, level, node.var_regex.pattern))\n\n                    line('if match is not None:')\n                    indent += 1\n                    line('params.update(match.groupdict())')\n\n                else:\n                    # NOTE(kgriffs): Simple nodes just capture the entire path\n                    # segment as the value for the param.\n                    line('params[\"%s\"] = path[%d]' % (node.var_name, level))\n\n                    # NOTE(kgriffs): We don't allow multiple simple var nodes\n                    # to exist at the same level, e.g.:\n                    #\n                    #   /foo/{id}/bar\n                    #   /foo/{name}/bar\n                    #\n                    assert len([_node for _node in nodes\n                                if _node.is_var and not _node.is_complex]) == 1\n                    found_simple = True\n\n            else:\n                # NOTE(kgriffs): Not a param, so must match exactly\n                line('if path[%d] == \"%s\":' % (level, node.raw_segment))\n                indent += 1\n\n            if node.resource is not None:\n                # NOTE(kgriffs): This is a valid route, so we will want to\n                # return the relevant information.\n                resource_idx = len(self._return_values)\n                self._return_values.append(node)\n\n            self._compile_tree(node.children, indent, level + 1, fast_return)\n\n            if node.resource is None:\n                if fast_return:\n                    line('return None')\n            else:\n                # NOTE(kgriffs): Make sure that we have consumed all of\n                # the segments for the requested route; otherwise we could\n                # mistakenly match \"/foo/23/bar\" against \"/foo/{id}\".\n                line('if path_len == %d:' % (level + 1))\n                line('return return_values[%d]' % resource_idx, 1)\n\n                if fast_return:\n                    line('return None')\n\n            indent = level_indent\n\n        if not found_simple and fast_return:\n            line('return None')\n\n    def _compile(self):\n        \"\"\"Generates Python code for entire routing tree.\n\n        The generated code is compiled and the resulting Python method is\n        returned.\n        \"\"\"\n        self._return_values = []\n        self._expressions = []\n        self._code_lines = [\n            'def find(path, return_values, expressions, params):',\n            TAB_STR + 'path_len = len(path)',\n        ]\n\n        self._compile_tree(self._roots)\n\n        self._code_lines.append(\n            # PERF(kgriffs): Explicit return of None is faster than implicit\n            TAB_STR + 'return None'\n        )\n\n        self._src = '\\n'.join(self._code_lines)\n\n        scope = {}\n        exec(compile(self._src, '<string>', 'exec'), scope)\n\n        return scope['find']\n\n\nclass CompiledRouterNode(object):\n    \"\"\"Represents a single URI segment in a URI.\"\"\"\n\n    _regex_vars = re.compile('{([-_a-zA-Z0-9]+)}')\n\n    def __init__(self, raw_segment, method_map=None, resource=None):\n        self.children = []\n\n        self.raw_segment = raw_segment\n        self.method_map = method_map\n        self.resource = resource\n\n        self.is_var = False\n        self.is_complex = False\n        self.var_name = None\n\n        seg = raw_segment.replace('.', '\\\\.')\n\n        matches = list(self._regex_vars.finditer(seg))\n        if matches:\n            self.is_var = True\n            # NOTE(richardolsson): if there is a single variable and it spans\n            # the entire segment, the segment is uncomplex and the variable\n            # name is simply the string contained within curly braces.\n            if len(matches) == 1 and matches[0].span() == (0, len(seg)):\n                self.is_complex = False\n                self.var_name = raw_segment[1:-1]\n            else:\n                # NOTE(richardolsson): Complex segments need to be converted\n                # into regular expressions will be used to match and extract\n                # variable values. The regular expressions contain both\n                # literal spans and named group expressions for the variables.\n                self.is_complex = True\n                seg_fields = []\n                prev_end_idx = 0\n                for match in matches:\n                    var_start_idx, var_end_idx = match.span()\n                    seg_fields.append(seg[prev_end_idx:var_start_idx])\n\n                    var_name = match.groups()[0].replace('-', '_')\n                    seg_fields.append('(?P<%s>[^/]+)' % var_name)\n\n                    prev_end_idx = var_end_idx\n\n                seg_fields.append(seg[prev_end_idx:])\n                seg_pattern = ''.join(seg_fields)\n                self.var_regex = re.compile(seg_pattern)\n        else:\n            self.is_var = False\n\n    def matches(self, segment):\n        \"\"\"Returns True if this node matches the supplied template segment.\"\"\"\n\n        return segment == self.raw_segment\n\n    def conflicts_with(self, segment):\n        \"\"\"Returns True if this node conflicts with a given template segment.\"\"\"\n\n        # NOTE(kgriffs): This method assumes that the caller has already\n        # checked if the segment matches. By definition, only unmatched\n        # segments may conflict, so there isn't any sense in calling\n        # conflicts_with in that case.\n        assert not self.matches(segment)\n\n        # NOTE(kgriffs): Possible combinations are as follows.\n        #\n        #   simple, simple ==> True\n        #   simple, complex ==> False\n        #   simple, string ==> False\n        #   complex, simple ==> False\n        #   complex, complex ==> (Depend)\n        #   complex, string ==> False\n        #   string, simple ==> False\n        #   string, complex ==> False\n        #   string, string ==> False\n        #\n        other = CompiledRouterNode(segment)\n\n        if self.is_var:\n            # NOTE(kgriffs & philiptzou): Falcon does not accept multiple\n            # simple var nodes exist at the same level as following:\n            #\n            #   /foo/{thing1}\n            #   /foo/{thing2}\n            #\n            # Nor two complex nodes like this:\n            #\n            #   /foo/{thing1}.{ext}\n            #   /foo/{thing2}.{ext}\n            #\n            # On the other hand, those are all OK:\n            #\n            #   /foo/{thing1}\n            #   /foo/all\n            #   /foo/{thing1}.{ext}\n            #   /foo/{thing2}.detail.{ext}\n            #\n            if self.is_complex:\n                if other.is_complex:\n                    return (self._regex_vars.sub('v', self.raw_segment) ==\n                            self._regex_vars.sub('v', segment))\n\n                return False\n            else:\n                return other.is_var and not other.is_complex\n\n        # NOTE(kgriffs): If self is a static string match, then all the cases\n        # for other are False, so no need to check.\n        return False\n", "path": "falcon/routing/compiled.py"}]}