We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
Completion: match terms in any order
[This regex](https://github.com/The-Compiler/qutebrowser/blob/master/qutebrowser/completion/models/sortfilter.py#L75), which is used to filter items for completion, constrains the match to the same order the terms are supplied by the user. I.e., "browser qute" does not match "qutebrowser". According to [this post](http://stackoverflow.com/a/18944925/4180822), this issue can be solved by constructing better regular expression using positive lookaheads. I think it's worthwhile to examine the performance impact of the solution, or find a different one.


--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `qutebrowser/completion/models/histcategory.py`
Content:
```
1 # vim: ft=python fileencoding=utf-8 sts=4 sw=4 et:
2 
3 # Copyright 2017 Ryan Roden-Corrent (rcorre) <ryan@rcorre.net>
4 #
5 # This file is part of qutebrowser.
6 #
7 # qutebrowser is free software: you can redistribute it and/or modify
8 # it under the terms of the GNU General Public License as published by
9 # the Free Software Foundation, either version 3 of the License, or
10 # (at your option) any later version.
11 #
12 # qutebrowser is distributed in the hope that it will be useful,
13 # but WITHOUT ANY WARRANTY; without even the implied warranty of
14 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 # GNU General Public License for more details.
16 #
17 # You should have received a copy of the GNU General Public License
18 # along with qutebrowser.  If not, see <http://www.gnu.org/licenses/>.
19 
20 """A completion category that queries the SQL History store."""
21 
22 import re
23 
24 from PyQt5.QtSql import QSqlQueryModel
25 
26 from qutebrowser.misc import sql
27 from qutebrowser.utils import debug
28 from qutebrowser.config import config
29 
30 
31 class HistoryCategory(QSqlQueryModel):
32 
33     """A completion category that queries the SQL History store."""
34 
35     def __init__(self, *, delete_func=None, parent=None):
36         """Create a new History completion category."""
37         super().__init__(parent=parent)
38         self.name = "History"
39 
40         # replace ' in timestamp-format to avoid breaking the query
41         timestamp_format = config.val.completion.timestamp_format
42         timefmt = ("strftime('{}', last_atime, 'unixepoch', 'localtime')"
43                    .format(timestamp_format.replace("'", "`")))
44 
45         self._query = sql.Query(' '.join([
46             "SELECT url, title, {}".format(timefmt),
47             "FROM CompletionHistory",
48             # the incoming pattern will have literal % and _ escaped with '\'
49             # we need to tell sql to treat '\' as an escape character
50             "WHERE ((url || title) LIKE :pat escape '\\')",
51             self._atime_expr(),
52             "ORDER BY last_atime DESC",
53         ]), forward_only=False)
54 
55         # advertise that this model filters by URL and title
56         self.columns_to_filter = [0, 1]
57         self.delete_func = delete_func
58 
59     def _atime_expr(self):
60         """If max_items is set, return an expression to limit the query."""
61         max_items = config.val.completion.web_history_max_items
62         # HistoryCategory should not be added to the completion in that case.
63         assert max_items != 0
64 
65         if max_items < 0:
66             return ''
67 
68         min_atime = sql.Query(' '.join([
69             'SELECT min(last_atime) FROM',
70             '(SELECT last_atime FROM CompletionHistory',
71             'ORDER BY last_atime DESC LIMIT :limit)',
72         ])).run(limit=max_items).value()
73 
74         if not min_atime:
75             # if there are no history items, min_atime may be '' (issue #2849)
76             return ''
77 
78         return "AND last_atime >= {}".format(min_atime)
79 
80     def set_pattern(self, pattern):
81         """Set the pattern used to filter results.
82 
83         Args:
84             pattern: string pattern to filter by.
85         """
86         # escape to treat a user input % or _ as a literal, not a wildcard
87         pattern = pattern.replace('%', '\\%')
88         pattern = pattern.replace('_', '\\_')
89         # treat spaces as wildcards to match any of the typed words
90         pattern = re.sub(r' +', '%', pattern)
91         pattern = '%{}%'.format(pattern)
92         with debug.log_time('sql', 'Running completion query'):
93             self._query.run(pat=pattern)
94         self.setQuery(self._query)
95 
96     def removeRows(self, row, _count, _parent=None):
97         """Override QAbstractItemModel::removeRows to re-run sql query."""
98         # re-run query to reload updated table
99         with debug.log_time('sql', 'Re-running completion query post-delete'):
100             self._query.run()
101         self.setQuery(self._query)
102         while self.rowCount() < row:
103             self.fetchMore()
104         return True
105
```
--- 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/qutebrowser/completion/models/histcategory.py b/qutebrowser/completion/models/histcategory.py
--- a/qutebrowser/completion/models/histcategory.py
+++ b/qutebrowser/completion/models/histcategory.py
@@ -19,8 +19,6 @@
 
 """A completion category that queries the SQL History store."""
 
-import re
-
 from PyQt5.QtSql import QSqlQueryModel
 
 from qutebrowser.misc import sql
@@ -36,21 +34,7 @@
         """Create a new History completion category."""
         super().__init__(parent=parent)
         self.name = "History"
-
-        # replace ' in timestamp-format to avoid breaking the query
-        timestamp_format = config.val.completion.timestamp_format
-        timefmt = ("strftime('{}', last_atime, 'unixepoch', 'localtime')"
-                   .format(timestamp_format.replace("'", "`")))
-
-        self._query = sql.Query(' '.join([
-            "SELECT url, title, {}".format(timefmt),
-            "FROM CompletionHistory",
-            # the incoming pattern will have literal % and _ escaped with '\'
-            # we need to tell sql to treat '\' as an escape character
-            "WHERE ((url || title) LIKE :pat escape '\\')",
-            self._atime_expr(),
-            "ORDER BY last_atime DESC",
-        ]), forward_only=False)
+        self._query = None
 
         # advertise that this model filters by URL and title
         self.columns_to_filter = [0, 1]
@@ -86,11 +70,36 @@
         # escape to treat a user input % or _ as a literal, not a wildcard
         pattern = pattern.replace('%', '\\%')
         pattern = pattern.replace('_', '\\_')
-        # treat spaces as wildcards to match any of the typed words
-        pattern = re.sub(r' +', '%', pattern)
-        pattern = '%{}%'.format(pattern)
+        words = ['%{}%'.format(w) for w in pattern.split(' ')]
+
+        # build a where clause to match all of the words in any order
+        # given the search term "a b", the WHERE clause would be:
+        # ((url || title) LIKE '%a%') AND ((url || title) LIKE '%b%')
+        where_clause = ' AND '.join(
+            "(url || title) LIKE :{} escape '\\'".format(i)
+            for i in range(len(words)))
+
+        # replace ' in timestamp-format to avoid breaking the query
+        timestamp_format = config.val.completion.timestamp_format
+        timefmt = ("strftime('{}', last_atime, 'unixepoch', 'localtime')"
+                   .format(timestamp_format.replace("'", "`")))
+
+        if not self._query or len(words) != len(self._query.boundValues()):
+            # if the number of words changed, we need to generate a new query
+            # otherwise, we can reuse the prepared query for performance
+            self._query = sql.Query(' '.join([
+                "SELECT url, title, {}".format(timefmt),
+                "FROM CompletionHistory",
+                # the incoming pattern will have literal % and _ escaped
+                # we need to tell sql to treat '\' as an escape character
+                'WHERE ({})'.format(where_clause),
+                self._atime_expr(),
+                "ORDER BY last_atime DESC",
+            ]), forward_only=False)
+
         with debug.log_time('sql', 'Running completion query'):
-            self._query.run(pat=pattern)
+            self._query.run(**{
+                str(i): w for i, w in enumerate(words)})
         self.setQuery(self._query)
 
     def removeRows(self, row, _count, _parent=None):

{"golden_diff": "diff --git a/qutebrowser/completion/models/histcategory.py b/qutebrowser/completion/models/histcategory.py\n--- a/qutebrowser/completion/models/histcategory.py\n+++ b/qutebrowser/completion/models/histcategory.py\n@@ -19,8 +19,6 @@\n \n \"\"\"A completion category that queries the SQL History store.\"\"\"\n \n-import re\n-\n from PyQt5.QtSql import QSqlQueryModel\n \n from qutebrowser.misc import sql\n@@ -36,21 +34,7 @@\n         \"\"\"Create a new History completion category.\"\"\"\n         super().__init__(parent=parent)\n         self.name = \"History\"\n-\n-        # replace ' in timestamp-format to avoid breaking the query\n-        timestamp_format = config.val.completion.timestamp_format\n-        timefmt = (\"strftime('{}', last_atime, 'unixepoch', 'localtime')\"\n-                   .format(timestamp_format.replace(\"'\", \"`\")))\n-\n-        self._query = sql.Query(' '.join([\n-            \"SELECT url, title, {}\".format(timefmt),\n-            \"FROM CompletionHistory\",\n-            # the incoming pattern will have literal % and _ escaped with '\\'\n-            # we need to tell sql to treat '\\' as an escape character\n-            \"WHERE ((url || title) LIKE :pat escape '\\\\')\",\n-            self._atime_expr(),\n-            \"ORDER BY last_atime DESC\",\n-        ]), forward_only=False)\n+        self._query = None\n \n         # advertise that this model filters by URL and title\n         self.columns_to_filter = [0, 1]\n@@ -86,11 +70,36 @@\n         # escape to treat a user input % or _ as a literal, not a wildcard\n         pattern = pattern.replace('%', '\\\\%')\n         pattern = pattern.replace('_', '\\\\_')\n-        # treat spaces as wildcards to match any of the typed words\n-        pattern = re.sub(r' +', '%', pattern)\n-        pattern = '%{}%'.format(pattern)\n+        words = ['%{}%'.format(w) for w in pattern.split(' ')]\n+\n+        # build a where clause to match all of the words in any order\n+        # given the search term \"a b\", the WHERE clause would be:\n+        # ((url || title) LIKE '%a%') AND ((url || title) LIKE '%b%')\n+        where_clause = ' AND '.join(\n+            \"(url || title) LIKE :{} escape '\\\\'\".format(i)\n+            for i in range(len(words)))\n+\n+        # replace ' in timestamp-format to avoid breaking the query\n+        timestamp_format = config.val.completion.timestamp_format\n+        timefmt = (\"strftime('{}', last_atime, 'unixepoch', 'localtime')\"\n+                   .format(timestamp_format.replace(\"'\", \"`\")))\n+\n+        if not self._query or len(words) != len(self._query.boundValues()):\n+            # if the number of words changed, we need to generate a new query\n+            # otherwise, we can reuse the prepared query for performance\n+            self._query = sql.Query(' '.join([\n+                \"SELECT url, title, {}\".format(timefmt),\n+                \"FROM CompletionHistory\",\n+                # the incoming pattern will have literal % and _ escaped\n+                # we need to tell sql to treat '\\' as an escape character\n+                'WHERE ({})'.format(where_clause),\n+                self._atime_expr(),\n+                \"ORDER BY last_atime DESC\",\n+            ]), forward_only=False)\n+\n         with debug.log_time('sql', 'Running completion query'):\n-            self._query.run(pat=pattern)\n+            self._query.run(**{\n+                str(i): w for i, w in enumerate(words)})\n         self.setQuery(self._query)\n \n     def removeRows(self, row, _count, _parent=None):\n", "issue": "Completion: match terms in any order\n[This regex](https://github.com/The-Compiler/qutebrowser/blob/master/qutebrowser/completion/models/sortfilter.py#L75), which is used to filter items for completion, constrains the match to the same order the terms are supplied by the user. I.e., \"browser qute\" does not match \"qutebrowser\". According to [this post](http://stackoverflow.com/a/18944925/4180822), this issue can be solved by constructing better regular expression using positive lookaheads. I think it's worthwhile to examine the performance impact of the solution, or find a different one.\n\n", "before_files": [{"content": "# vim: ft=python fileencoding=utf-8 sts=4 sw=4 et:\n\n# Copyright 2017 Ryan Roden-Corrent (rcorre) <ryan@rcorre.net>\n#\n# This file is part of qutebrowser.\n#\n# qutebrowser is free software: you can redistribute it and/or modify\n# it under the terms of the GNU General Public License as published by\n# the Free Software Foundation, either version 3 of the License, or\n# (at your option) any later version.\n#\n# qutebrowser is distributed in the hope that it will be useful,\n# but WITHOUT ANY WARRANTY; without even the implied warranty of\n# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n# GNU General Public License for more details.\n#\n# You should have received a copy of the GNU General Public License\n# along with qutebrowser.  If not, see <http://www.gnu.org/licenses/>.\n\n\"\"\"A completion category that queries the SQL History store.\"\"\"\n\nimport re\n\nfrom PyQt5.QtSql import QSqlQueryModel\n\nfrom qutebrowser.misc import sql\nfrom qutebrowser.utils import debug\nfrom qutebrowser.config import config\n\n\nclass HistoryCategory(QSqlQueryModel):\n\n    \"\"\"A completion category that queries the SQL History store.\"\"\"\n\n    def __init__(self, *, delete_func=None, parent=None):\n        \"\"\"Create a new History completion category.\"\"\"\n        super().__init__(parent=parent)\n        self.name = \"History\"\n\n        # replace ' in timestamp-format to avoid breaking the query\n        timestamp_format = config.val.completion.timestamp_format\n        timefmt = (\"strftime('{}', last_atime, 'unixepoch', 'localtime')\"\n                   .format(timestamp_format.replace(\"'\", \"`\")))\n\n        self._query = sql.Query(' '.join([\n            \"SELECT url, title, {}\".format(timefmt),\n            \"FROM CompletionHistory\",\n            # the incoming pattern will have literal % and _ escaped with '\\'\n            # we need to tell sql to treat '\\' as an escape character\n            \"WHERE ((url || title) LIKE :pat escape '\\\\')\",\n            self._atime_expr(),\n            \"ORDER BY last_atime DESC\",\n        ]), forward_only=False)\n\n        # advertise that this model filters by URL and title\n        self.columns_to_filter = [0, 1]\n        self.delete_func = delete_func\n\n    def _atime_expr(self):\n        \"\"\"If max_items is set, return an expression to limit the query.\"\"\"\n        max_items = config.val.completion.web_history_max_items\n        # HistoryCategory should not be added to the completion in that case.\n        assert max_items != 0\n\n        if max_items < 0:\n            return ''\n\n        min_atime = sql.Query(' '.join([\n            'SELECT min(last_atime) FROM',\n            '(SELECT last_atime FROM CompletionHistory',\n            'ORDER BY last_atime DESC LIMIT :limit)',\n        ])).run(limit=max_items).value()\n\n        if not min_atime:\n            # if there are no history items, min_atime may be '' (issue #2849)\n            return ''\n\n        return \"AND last_atime >= {}\".format(min_atime)\n\n    def set_pattern(self, pattern):\n        \"\"\"Set the pattern used to filter results.\n\n        Args:\n            pattern: string pattern to filter by.\n        \"\"\"\n        # escape to treat a user input % or _ as a literal, not a wildcard\n        pattern = pattern.replace('%', '\\\\%')\n        pattern = pattern.replace('_', '\\\\_')\n        # treat spaces as wildcards to match any of the typed words\n        pattern = re.sub(r' +', '%', pattern)\n        pattern = '%{}%'.format(pattern)\n        with debug.log_time('sql', 'Running completion query'):\n            self._query.run(pat=pattern)\n        self.setQuery(self._query)\n\n    def removeRows(self, row, _count, _parent=None):\n        \"\"\"Override QAbstractItemModel::removeRows to re-run sql query.\"\"\"\n        # re-run query to reload updated table\n        with debug.log_time('sql', 'Re-running completion query post-delete'):\n            self._query.run()\n        self.setQuery(self._query)\n        while self.rowCount() < row:\n            self.fetchMore()\n        return True\n", "path": "qutebrowser/completion/models/histcategory.py"}], "after_files": [{"content": "# vim: ft=python fileencoding=utf-8 sts=4 sw=4 et:\n\n# Copyright 2017 Ryan Roden-Corrent (rcorre) <ryan@rcorre.net>\n#\n# This file is part of qutebrowser.\n#\n# qutebrowser is free software: you can redistribute it and/or modify\n# it under the terms of the GNU General Public License as published by\n# the Free Software Foundation, either version 3 of the License, or\n# (at your option) any later version.\n#\n# qutebrowser is distributed in the hope that it will be useful,\n# but WITHOUT ANY WARRANTY; without even the implied warranty of\n# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n# GNU General Public License for more details.\n#\n# You should have received a copy of the GNU General Public License\n# along with qutebrowser.  If not, see <http://www.gnu.org/licenses/>.\n\n\"\"\"A completion category that queries the SQL History store.\"\"\"\n\nfrom PyQt5.QtSql import QSqlQueryModel\n\nfrom qutebrowser.misc import sql\nfrom qutebrowser.utils import debug\nfrom qutebrowser.config import config\n\n\nclass HistoryCategory(QSqlQueryModel):\n\n    \"\"\"A completion category that queries the SQL History store.\"\"\"\n\n    def __init__(self, *, delete_func=None, parent=None):\n        \"\"\"Create a new History completion category.\"\"\"\n        super().__init__(parent=parent)\n        self.name = \"History\"\n        self._query = None\n\n        # advertise that this model filters by URL and title\n        self.columns_to_filter = [0, 1]\n        self.delete_func = delete_func\n\n    def _atime_expr(self):\n        \"\"\"If max_items is set, return an expression to limit the query.\"\"\"\n        max_items = config.val.completion.web_history_max_items\n        # HistoryCategory should not be added to the completion in that case.\n        assert max_items != 0\n\n        if max_items < 0:\n            return ''\n\n        min_atime = sql.Query(' '.join([\n            'SELECT min(last_atime) FROM',\n            '(SELECT last_atime FROM CompletionHistory',\n            'ORDER BY last_atime DESC LIMIT :limit)',\n        ])).run(limit=max_items).value()\n\n        if not min_atime:\n            # if there are no history items, min_atime may be '' (issue #2849)\n            return ''\n\n        return \"AND last_atime >= {}\".format(min_atime)\n\n    def set_pattern(self, pattern):\n        \"\"\"Set the pattern used to filter results.\n\n        Args:\n            pattern: string pattern to filter by.\n        \"\"\"\n        # escape to treat a user input % or _ as a literal, not a wildcard\n        pattern = pattern.replace('%', '\\\\%')\n        pattern = pattern.replace('_', '\\\\_')\n        words = ['%{}%'.format(w) for w in pattern.split(' ')]\n\n        # build a where clause to match all of the words in any order\n        # given the search term \"a b\", the WHERE clause would be:\n        # ((url || title) LIKE '%a%') AND ((url || title) LIKE '%b%')\n        where_clause = ' AND '.join(\n            \"(url || title) LIKE :{} escape '\\\\'\".format(i)\n            for i in range(len(words)))\n\n        # replace ' in timestamp-format to avoid breaking the query\n        timestamp_format = config.val.completion.timestamp_format\n        timefmt = (\"strftime('{}', last_atime, 'unixepoch', 'localtime')\"\n                   .format(timestamp_format.replace(\"'\", \"`\")))\n\n        if not self._query or len(words) != len(self._query.boundValues()):\n            # if the number of words changed, we need to generate a new query\n            # otherwise, we can reuse the prepared query for performance\n            self._query = sql.Query(' '.join([\n                \"SELECT url, title, {}\".format(timefmt),\n                \"FROM CompletionHistory\",\n                # the incoming pattern will have literal % and _ escaped\n                # we need to tell sql to treat '\\' as an escape character\n                'WHERE ({})'.format(where_clause),\n                self._atime_expr(),\n                \"ORDER BY last_atime DESC\",\n            ]), forward_only=False)\n\n        with debug.log_time('sql', 'Running completion query'):\n            self._query.run(**{\n                str(i): w for i, w in enumerate(words)})\n        self.setQuery(self._query)\n\n    def removeRows(self, row, _count, _parent=None):\n        \"\"\"Override QAbstractItemModel::removeRows to re-run sql query.\"\"\"\n        # re-run query to reload updated table\n        with debug.log_time('sql', 'Re-running completion query post-delete'):\n            self._query.run()\n        self.setQuery(self._query)\n        while self.rowCount() < row:\n            self.fetchMore()\n        return True\n", "path": "qutebrowser/completion/models/histcategory.py"}]}