Repository: falconry/falcon

Issue:
uri.parse_query_string() incorrectly parses an empty string
cf
```python
>>> from urllib import parse
>>> from falcon.util import uri
>>> parse.parse_qs('', keep_blank_values=True)
{}
>>> uri.parse_query_string('', keep_blank=True)
{'': ''}
```

The good ol' _an empty string splits to a list with one empty string item_ trick is biting us here as I understand.

Discussion:
codecov[bot]: # [Codecov](https://codecov.io/gh/falconry/falcon/pull/1604?src=pr&el=h1) Report
> Merging [#1604](https://codecov.io/gh/falconry/falcon/pull/1604?src=pr&el=desc) into [master](https://codecov.io/gh/falconry/falcon/commit/4df7706eb69f2064ee00a4d5280505d893f27638?src=pr&el=desc) will **not change** coverage.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/falconry/falcon/pull/1604/graphs/tree.svg?width=650&token=zOtkfNQ3h6&height=150&src=pr)](https://codecov.io/gh/falconry/falcon/pull/1604?src=pr&el=tree)

```diff
@@          Coverage Diff           @@
##           master   #1604   +/-   ##
======================================
  Coverage     100%    100%           
======================================
  Files          40      40           
  Lines        2595    2601    +6     
  Branches      394     393    -1     
======================================
+ Hits         2595    2601    +6
```


| [Impacted Files](https://codecov.io/gh/falconry/falcon/pull/1604?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [falcon/media/urlencoded.py](https://codecov.io/gh/falconry/falcon/pull/1604/diff?src=pr&el=tree#diff-ZmFsY29uL21lZGlhL3VybGVuY29kZWQucHk=) | `100% <ø> (ø)` | :arrow_up: |
| [falcon/util/uri.py](https://codecov.io/gh/falconry/falcon/pull/1604/diff?src=pr&el=tree#diff-ZmFsY29uL3V0aWwvdXJpLnB5) | `100% <100%> (ø)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/falconry/falcon/pull/1604?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/falconry/falcon/pull/1604?src=pr&el=footer). Last update [4df7706...58dee5d](https://codecov.io/gh/falconry/falcon/pull/1604?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

vytas7: Note that if the approach is acceptable, we could in the future easily define `parse_query_bytes` or similar to further optimize deserialization directly from the payload bytes.

We could quickly do the ASCII check by simply verifying every quadword in the payload `& 0x8080808080808080LL` is zero or something in that vein. 
vytas7: @kgriffs Hopefully ready for another review now!

I haven't done anything about boolean operation grouping in the pure Python fix though. I'm thinking to myself it's largely irrelevant for CPython users since they should look to the presented cythonized variant anyway; so I'll benchmark performance characteristics on PyPy3 and make a decision based on that.

Patch:
diff --git a/.travis.yml b/.travis.yml
index fbe74ee..3519441 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -27,6 +27,11 @@ matrix:
           env: TOXENV=mypy
         - python: 3.8
           env: TOXENV=py38_cython
+        - python: 3.8
+          # NOTE(vytas): Big-endian architecture
+          arch: s390x
+          os: linux
+          env: TOXENV=py38_cython
         - python: 3.8
           env: TOXENV=py38_smoke
         - python: 3.8
@@ -52,8 +57,8 @@ notifications:
     on_failure: always
 
 before_install:
-  - sudo apt-get update
-  - sudo apt-get install -y libunwind-dev
+  # NOTE(vytas): libunwind-dev does not exist for s390x in Ubuntu 16.04
+  - if [[ `uname -m` == *86* ]]; then sudo apt-get update && sudo apt-get install -y libunwind-dev; fi
   - pip install codecov
 
 after_success:
diff --git a/docs/_newsfragments/1600-parse-empty-query-string.bugfix.rst b/docs/_newsfragments/1600-parse-empty-query-string.bugfix.rst
new file mode 100644
index 0000000..0566aab
--- /dev/null
+++ b/docs/_newsfragments/1600-parse-empty-query-string.bugfix.rst
@@ -0,0 +1,2 @@
+The ``uri.parse_query_string()`` utility function is now correctly parsing an
+empty string as ``{}``.
diff --git a/falcon/cyutil/uri.pyx b/falcon/cyutil/uri.pyx
new file mode 100644
index 0000000..47662fb
--- /dev/null
+++ b/falcon/cyutil/uri.pyx
@@ -0,0 +1,253 @@
+# Copyright 2019 by Vytautas Liuolia.
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#    http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+
+from cpython.mem cimport PyMem_Malloc, PyMem_Free
+from libc.string cimport memcpy
+
+
+cdef list build_hex_table():
+    cdef list result = [-1] * 0x10000
+    for ch1 in '0123456789abcdefABCDEF':
+        for ch2 in '0123456789abcdefABCDEF':
+            try:
+                result[(ord(ch1) << 8) | ord(ch2)] = int(ch1 + ch2, 16)
+            except ValueError:
+                pass
+
+    return result
+
+
+# PERF(vytas): Cache hex characters lookup table
+cdef int[0x10000] HEX_CHARS
+HEX_CHARS[:] = build_hex_table()
+
+# PERF(vytas): Cache an empty string object.
+cdef EMPTY_STRING = u''
+
+
+cdef inline int cy_decode_hex(unsigned char nibble1, unsigned char nibble2):
+    return HEX_CHARS[(nibble1 << 8) | nibble2]
+
+
+cdef unicode cy_decode(unsigned char* data, Py_ssize_t start, Py_ssize_t end,
+                       Py_ssize_t encoded_start, bint unquote_plus):
+    # PERF(vytas): encoded_start being -1 signifies that the caller
+    #   (cy_parse_query_string) has already verified that no encoding
+    #   characters exist in the provided substring data[start:end].
+    if encoded_start < 0:
+        return data[start:end].decode()
+
+    cdef unsigned char* result
+    cdef Py_ssize_t src_start = start
+    cdef Py_ssize_t dst_start = 0
+    cdef Py_ssize_t pos
+    cdef int decoded
+
+    result = <unsigned char*> PyMem_Malloc(end - start)
+    if not result:
+        raise MemoryError()
+
+    try:
+        for pos in range(encoded_start, end):
+            if data[pos] not in b'+%':
+                continue
+
+            if src_start < pos:
+                memcpy(result + dst_start, data + src_start,
+                       pos - src_start)
+
+            dst_start += pos - src_start
+            src_start = pos
+
+            if data[pos] == b'+' and unquote_plus:
+                result[dst_start] = b' '
+                dst_start += 1
+                src_start += 1
+                continue
+
+            # NOTE(vytas): Else %
+            if pos < end - 2:
+                decoded = cy_decode_hex(data[pos+1], data[pos+2])
+                if decoded < 0:
+                    continue
+
+                # NOTE(vytas): Succeeded decoding a byte
+                result[dst_start] = decoded
+                dst_start += 1
+                src_start += 3
+                # NOTE(vytas): It is somewhat ugly to wind the loop variable
+                #   like that, but hopefully it is a lesser sin in C.
+                pos += 2
+
+        if src_start < end:
+            memcpy(result + dst_start, data + src_start,
+                   end - src_start)
+
+        return result[:dst_start + end - src_start].decode('utf-8', 'replace')
+
+    finally:
+        PyMem_Free(result)
+
+
+cdef cy_handle_csv(dict result, bint keep_blank, unicode key, unicode value):
+    # NOTE(kgriffs): Falcon supports a more compact form of lists, in which the
+    # elements are comma-separated and assigned to a single param instance. If
+    # it turns out that very few people use this, it can be deprecated at some
+    # point.
+
+    # NOTE(vytas): This case of csv=True is no longer the default request
+    # option so we largely reimplement the unoptimized Python version here.
+
+    cdef old_value = result.get(key)
+
+    # NOTE(steffgrez): Falcon decodes value at the last moment. So query parser
+    # won't mix up between percent-encoded comma (as value) and comma-separated
+    # list (as reserved character for sub-delimiter).
+    if old_value is None:
+        if ',' in value:
+            if not keep_blank:
+                # NOTE(kgriffs): Normalize the result in the case that some
+                # elements are empty strings, such that the result will be the
+                # same for 'foo=1,,3' as 'foo=1&foo=&foo=3'.
+                result[key] = [decode(element) for element in value.split(',')
+                               if element]
+            else:
+                result[key] = [decode(element) for element in value.split(',')]
+        else:
+            result[key] = decode(value)
+
+    elif isinstance(old_value, list):
+        old_value.append(decode(value))
+    else:
+        result[key] = [old_value, decode(value)]
+
+
+cdef cy_parse_query_string(unsigned char* data, Py_ssize_t length,
+                           bint keep_blank, bint csv):
+    cdef Py_ssize_t pos
+    cdef unsigned char current
+
+    cdef Py_ssize_t start = 0
+    cdef Py_ssize_t encoded_start_key = -1
+    cdef Py_ssize_t encoded_start_val = -1
+    cdef Py_ssize_t partition = -1
+
+    cdef unicode key
+    cdef unicode value
+    cdef old_value
+    cdef dict result = {}
+
+    for pos in range(length):
+        # PERF(vytas): Quick check if we need to do anything special with the
+        #   current character.
+        #   Cython should translate this check into a switch statement.
+        if data[pos] not in b'%&+,=':
+            continue
+
+        current = data[pos]
+
+        if current == b'&':
+            # TODO(vytas): DRY this with the "if length > start" block below.
+            #   Keep them in sync until they are improved to share code.
+            if pos > start:
+                if partition >= 0:
+                    key = cy_decode(data, start, partition, encoded_start_key, True)
+                    if csv and encoded_start_val >= 0:
+                        cy_handle_csv(result, keep_blank, key,
+                                      data[partition+1:pos].decode())
+                        start = pos + 1
+                        encoded_start_key = -1
+                        encoded_start_val = -1
+                        partition = -1
+                        continue
+
+                    value = cy_decode(data, partition+1, pos, encoded_start_val, True)
+                else:
+                    key = cy_decode(data, start, pos, encoded_start_key, True)
+                    value = EMPTY_STRING
+
+                if value is not EMPTY_STRING or keep_blank:
+                    old_value = result.get(key)
+
+                    if old_value is None:
+                        result[key] = value
+                    elif isinstance(old_value, list):
+                        old_value.append(value)
+                    else:
+                        result[key] = [old_value, value]
+
+            start = pos + 1
+            encoded_start_key = -1
+            encoded_start_val = -1
+            partition = -1
+            continue
+
+        if current == b'=':
+            if partition < 0:
+                partition = pos
+            continue
+
+        # else: current in b'%+,'
+
+        # PERF(vytas): Record positions of the first encoded character, if any.
+        #  This will be used to determine where to start decoding, if at all.
+        if partition < 0:
+            if encoded_start_key < 0:
+                encoded_start_key = pos
+        else:
+            if encoded_start_val < 0:
+                encoded_start_val = pos
+
+    # NOTE(vytas): This block is largely the same (although not identical as it
+    #   does not need to compute the endoded_start_* values) as the above
+    #   "if pos > start" (see also the DRY TODO note earlier in this function).
+    #   Keep them in sync until they are improved to share code.
+    if length > start:
+        if partition >= 0:
+            key = cy_decode(data, start, partition, encoded_start_key, True)
+            if csv and encoded_start_val >= 0:
+                cy_handle_csv(result, keep_blank, key,
+                              data[partition+1:length].decode())
+                return result
+
+            value = cy_decode(data, partition+1, length, encoded_start_val, True)
+        else:
+            key = cy_decode(data, start, length, encoded_start_key, True)
+            value = EMPTY_STRING
+
+        if value is not EMPTY_STRING or keep_blank:
+            old_value = result.get(key)
+
+            if old_value is None:
+                result[key] = value
+            elif isinstance(old_value, list):
+                old_value.append(value)
+            else:
+                result[key] = [old_value, value]
+
+    return result
+
+
+def parse_query_string(unicode query_string not None, bint keep_blank=False,
+                       bint csv=True):
+    cdef bytes byte_string = query_string.encode('utf-8')
+    cdef unsigned char* data = byte_string
+    return cy_parse_query_string(data, len(byte_string), keep_blank, csv)
+
+
+def decode(unicode encoded_uri not None, bint unquote_plus=True):
+    cdef bytes byte_string = encoded_uri.encode('utf-8')
+    cdef unsigned char* data = byte_string
+    return cy_decode(data, 0, len(byte_string), 0, unquote_plus)
diff --git a/falcon/media/urlencoded.py b/falcon/media/urlencoded.py
index 95228fd..5aa7dae 100644
--- a/falcon/media/urlencoded.py
+++ b/falcon/media/urlencoded.py
@@ -35,12 +35,6 @@ class URLEncodedFormHandler(BaseHandler):
         # catch malicious input.
         body = body.decode('ascii')
 
-        # TODO(vytas): We are not short-circuiting here for performance (as
-        #   empty URL-encoded payload should not be a common case), but to work
-        #   around #1600
-        if not body:
-            return {}
-
         return parse_query_string(body,
                                   keep_blank=self.keep_blank,
                                   csv=self.csv)
diff --git a/falcon/util/uri.py b/falcon/util/uri.py
index 6dcefe9..9af38b6 100644
--- a/falcon/util/uri.py
+++ b/falcon/util/uri.py
@@ -24,6 +24,16 @@ in the `falcon` module, and so must be explicitly imported::
 
 """
 
+try:
+    from falcon.cyutil.uri import (
+        decode as _cy_decode,
+        parse_query_string as _cy_parse_query_string,
+    )
+except ImportError:
+    _cy_decode = None
+    _cy_parse_query_string = None
+
+
 # NOTE(kgriffs): See also RFC 3986
 _UNRESERVED = ('ABCDEFGHIJKLMNOPQRSTUVWXYZ'
                'abcdefghijklmnopqrstuvwxyz'
@@ -264,7 +274,7 @@ def parse_query_string(query_string, keep_blank=False, csv=True):
     # both short and long query strings. Tested on CPython 3.4.
     for field in query_string.split('&'):
         k, _, v = field.partition('=')
-        if not (v or keep_blank):
+        if not v and (not keep_blank or not k):
             continue
 
         # Note(steffgrez): Falcon first decode name parameter for handle
@@ -394,3 +404,19 @@ def unquote_string(quoted):
     else:
         return '\\'.join([q.replace('\\', '')
                           for q in tmp_quoted.split(r'\\')])
+
+
+# TODO(vytas): Restructure this in favour of a cleaner way to hoist the pure
+# Cython functions into this module.
+decode = _cy_decode or decode  # NOQA
+parse_query_string = _cy_parse_query_string or parse_query_string  # NOQA
+
+
+__all__ = [
+    'decode',
+    'encode',
+    'encode_value',
+    'parse_host',
+    'parse_query_string',
+    'unquote_string',
+]
diff --git a/setup.py b/setup.py
index 166deb1..5de9007 100644
--- a/setup.py
+++ b/setup.py
@@ -39,31 +39,39 @@ else:
         CYTHON = False
 
 if CYTHON:
-    def list_modules(dirname):
-        filenames = glob.glob(path.join(dirname, '*.py'))
+    def list_modules(dirname, pattern):
+        filenames = glob.glob(path.join(dirname, pattern))
 
         module_names = []
         for name in filenames:
             module, ext = path.splitext(path.basename(name))
             if module != '__init__':
-                module_names.append(module)
+                module_names.append((module, ext))
 
         return module_names
 
     package_names = [
         'falcon',
+        'falcon.cyutil',
         'falcon.media',
         'falcon.routing',
         'falcon.util',
         'falcon.vendor.mimeparse',
     ]
+
+    cython_package_names = frozenset([
+        'falcon.cyutil',
+    ])
+
     ext_modules = [
         Extension(
             package + '.' + module,
-            [path.join(*(package.split('.') + [module + '.py']))]
+            [path.join(*(package.split('.') + [module + ext]))]
         )
         for package in package_names
-        for module in list_modules(path.join(MYDIR, *package.split('.')))
+        for module, ext in list_modules(
+            path.join(MYDIR, *package.split('.')),
+            ('*.pyx' if package in cython_package_names else '*.py'))
     ]
 
     cmdclass = {'build_ext': build_ext}


Test patch:
diff --git a/tests/test_utils.py b/tests/test_utils.py
index 893f82a..0938546 100644
--- a/tests/test_utils.py
+++ b/tests/test_utils.py
@@ -2,6 +2,7 @@
 
 from datetime import datetime
 import functools
+import itertools
 import random
 from urllib.parse import quote, unquote_plus
 
@@ -201,6 +202,15 @@ class TestFalconUtils:
             'http://example.com?x=ab%2Bcd%3D42%2C9'
         ) == 'http://example.com?x=ab+cd=42,9'
 
+    @pytest.mark.parametrize('encoded,expected', [
+        ('+%80', ' �'),
+        ('+++%FF+++', '   �   '),  # impossible byte
+        ('%fc%83%bf%bf%bf%bf', '������'),  # overlong sequence
+        ('%ed%ae%80%ed%b0%80', '������'),  # paired UTF-16 surrogates
+    ])
+    def test_uri_decode_replace_bad_unicode(self, encoded, expected):
+        assert uri.decode(encoded) == expected
+
     def test_uri_decode_unquote_plus(self):
         assert uri.decode('/disk/lost+found/fd0') == '/disk/lost found/fd0'
         assert uri.decode('/disk/lost+found/fd0', unquote_plus=True) == (
@@ -250,7 +260,7 @@ class TestFalconUtils:
         assert uri.unquote_string('"partial-quoted"') == 'partial-quoted'
 
     def test_parse_query_string(self):
-        query_strinq = (
+        query_string = (
             'a=http%3A%2F%2Ffalconframework.org%3Ftest%3D1'
             '&b=%7B%22test1%22%3A%20%22data1%22%'
             '2C%20%22test2%22%3A%20%22data2%22%7D'
@@ -263,7 +273,7 @@ class TestFalconUtils:
         decoded_url = 'http://falconframework.org?test=1'
         decoded_json = '{"test1": "data1", "test2": "data2"}'
 
-        result = uri.parse_query_string(query_strinq)
+        result = uri.parse_query_string(query_string)
         assert result['a'] == decoded_url
         assert result['b'] == decoded_json
         assert result['c'] == ['1', '2', '3']
@@ -272,7 +282,7 @@ class TestFalconUtils:
         assert result['f'] == ['a', 'a=b']
         assert result['é'] == 'a=b'
 
-        result = uri.parse_query_string(query_strinq, True)
+        result = uri.parse_query_string(query_string, True)
         assert result['a'] == decoded_url
         assert result['b'] == decoded_json
         assert result['c'] == ['1', '2', '3']
@@ -281,6 +291,43 @@ class TestFalconUtils:
         assert result['f'] == ['a', 'a=b']
         assert result['é'] == 'a=b'
 
+    @pytest.mark.parametrize('query_string,keep_blank,expected', [
+        ('', True, {}),
+        ('', False, {}),
+        ('flag1&&&&&flag2&&&', True, {'flag1': '', 'flag2': ''}),
+        ('flag1&&&&&flag2&&&', False, {}),
+        ('malformed=%FG%1%Hi%%%a', False, {'malformed': '%FG%1%Hi%%%a'}),
+        ('=', False, {}),
+        ('==', False, {'': '='}),
+        (
+            '%==+==&&&&&&&&&%%==+=&&&&&&%0g%=%=',
+            False,
+            {'%': '= ==', '%%': '= =', '%0g%': '%='},
+        ),
+        ('%=&%%=&&%%%=', False, {}),
+        ('%=&%%=&&%%%=', True, {'%': '', '%%': '', '%%%': ''}),
+        ('+=&%+=&&%++=', True, {' ': '', '% ': '', '%  ': ''}),
+        ('=x=&=x=+1=x=&%=x', False, {'': ['x=', 'x= 1=x='], '%': 'x'}),
+        (
+            ''.join(itertools.chain.from_iterable(
+                itertools.permutations('%=+&', 4))),
+            False,
+            {
+                '': ['%', ' %', '%', ' ', ' =%', '%', '% ', ' %'],
+                ' ': ['=% ', ' %', '%'],
+                '%': [' ', ' ', ' '],
+            },
+        ),
+        # NOTE(vytas): Sanity check that we do not accidentally use C-strings
+        #   anywhere in the cythonized variant.
+        ('%%%\x00%\x00==\x00\x00==', True, {'%%%\x00%\x00': '=\x00\x00=='}),
+        ('spade=♠&spade=♠', False, {'spade': ['♠', '♠']}),  # Unicode query
+    ])
+    def test_parse_query_string_edge_cases(
+            self, query_string, keep_blank, expected):
+        assert uri.parse_query_string(query_string, keep_blank=keep_blank) == (
+            expected)
+
     def test_parse_host(self):
         assert uri.parse_host('::1') == ('::1', None)
         assert uri.parse_host('2001:ODB8:AC10:FE01::') == ('2001:ODB8:AC10:FE01::', None)