prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <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.
  
  
  </issue>
  <code>
  [start of qutebrowser/completion/models/histcategory.py]
  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 of qutebrowser/completion/models/histcategory.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: 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):
  
verification_info: {"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"}]}