Ensure completions are sorted after filtering.

I previously removed the sorting logic from SortFilter thinking it was
unnecessary if we construct the model with a sorted list. However, this
only worked when no pattern was set, and the items are misordered as
soon as a pattern is input.

This patch reintroduces alpha-sorting, which can be disabled by passing
sort=False to the ListCategory constructor. The session completion test
had to be tweaked as it simulated the incorrect assumption that the
session list is not alpha-ordered; sessions come out of the
session-manager pre-sorted so we may as well use alpha-sorting in the
session completion model.

Resolves #3156.

(cherry picked from commit 47447c047ad7374e2b7ec4bb4775eb74f7f5f6a8)

6 files changed, 47 insertions, 22 deletions

diff --git a/qutebrowser/completion/models/configmodel.py b/qutebrowser/completion/models/configmodel.py
index bb1f16758..f1d706cd5 100644
--- a/qutebrowser/completion/models/configmodel.py
+++ b/qutebrowser/completion/models/configmodel.py
@@ -29,7 +29,7 @@ def option(*, info):
     model = completionmodel.CompletionModel(column_widths=(20, 70, 10))
     options = ((opt.name, opt.description, info.config.get_str(opt.name))
                for opt in configdata.DATA.values())
-    model.add_category(listcategory.ListCategory("Options", sorted(options)))
+    model.add_category(listcategory.ListCategory("Options", options))
     return model
 
 
@@ -39,7 +39,7 @@ def customized_option(*, info):
     options = ((opt.name, opt.description, info.config.get_str(opt.name))
                for opt, _value in info.config)
     model.add_category(listcategory.ListCategory("Customized options",
-                                                 sorted(options)))
+                                                 options))
     return model
 
 
@@ -66,8 +66,7 @@ def value(optname, *_values, info):
 
     vals = opt.typ.complete()
     if vals is not None:
-        model.add_category(listcategory.ListCategory("Completions",
-                                                     sorted(vals)))
+        model.add_category(listcategory.ListCategory("Completions", vals))
     return model
 
 
diff --git a/qutebrowser/completion/models/listcategory.py b/qutebrowser/completion/models/listcategory.py
index 111cd8358..657ae97aa 100644
--- a/qutebrowser/completion/models/listcategory.py
+++ b/qutebrowser/completion/models/listcategory.py
@@ -31,7 +31,7 @@ class ListCategory(QSortFilterProxyModel):
 
     """Expose a list of items as a category for the CompletionModel."""
 
-    def __init__(self, name, items, delete_func=None, parent=None):
+    def __init__(self, name, items, sort=True, delete_func=None, parent=None):
         super().__init__(parent)
         self.name = name
         self.srcmodel = QStandardItemModel(parent=self)
@@ -43,6 +43,7 @@ class ListCategory(QSortFilterProxyModel):
             self.srcmodel.appendRow([QStandardItem(x) for x in item])
         self.setSourceModel(self.srcmodel)
         self.delete_func = delete_func
+        self._sort = sort
 
     def set_pattern(self, val):
         """Setter for pattern.
@@ -60,19 +61,33 @@ class ListCategory(QSortFilterProxyModel):
         sortcol = 0
         self.sort(sortcol)
 
-    def lessThan(self, _lindex, rindex):
+    def lessThan(self, lindex, rindex):
         """Custom sorting implementation.
 
-        Prefers all items which start with self._pattern. Other than that, keep
-        items in their original order.
+        Prefers all items which start with self._pattern. Other than that, uses
+        normal Python string sorting.
 
         Args:
-            _lindex: The QModelIndex of the left item (*left* < right)
+            lindex: The QModelIndex of the left item (*left* < right)
             rindex: The QModelIndex of the right item (left < *right*)
 
         Return:
             True if left < right, else False
         """
+        qtutils.ensure_valid(lindex)
         qtutils.ensure_valid(rindex)
+
+        left = self.srcmodel.data(lindex)
         right = self.srcmodel.data(rindex)
-        return not right.startswith(self._pattern)
+
+        leftstart = left.startswith(self._pattern)
+        rightstart = right.startswith(self._pattern)
+
+        if leftstart and not rightstart:
+            return True
+        elif rightstart and not leftstart:
+            return False
+        elif self._sort:
+            return left < right
+        else:
+            return False
diff --git a/qutebrowser/completion/models/miscmodels.py b/qutebrowser/completion/models/miscmodels.py
index 3244c7bf3..7732fef45 100644
--- a/qutebrowser/completion/models/miscmodels.py
+++ b/qutebrowser/completion/models/miscmodels.py
@@ -43,7 +43,7 @@ def helptopic(*, info):
                 for opt in configdata.DATA.values())
 
     model.add_category(listcategory.ListCategory("Commands", cmdlist))
-    model.add_category(listcategory.ListCategory("Settings", sorted(settings)))
+    model.add_category(listcategory.ListCategory("Settings", settings))
     return model
 
 
@@ -59,7 +59,8 @@ def quickmark(*, info=None):  # pylint: disable=unused-argument
     model = completionmodel.CompletionModel(column_widths=(30, 70, 0))
     marks = objreg.get('quickmark-manager').marks.items()
     model.add_category(listcategory.ListCategory('Quickmarks', marks,
-                                                 delete_func=delete))
+                                                 delete_func=delete,
+                                                 sort=False))
     return model
 
 
@@ -75,7 +76,8 @@ def bookmark(*, info=None):  # pylint: disable=unused-argument
     model = completionmodel.CompletionModel(column_widths=(30, 70, 0))
     marks = objreg.get('bookmark-manager').marks.items()
     model.add_category(listcategory.ListCategory('Bookmarks', marks,
-                                                 delete_func=delete))
+                                                 delete_func=delete,
+                                                 sort=False))
     return model
 
 
diff --git a/qutebrowser/completion/models/urlmodel.py b/qutebrowser/completion/models/urlmodel.py
index e7f3086c4..617fa74b5 100644
--- a/qutebrowser/completion/models/urlmodel.py
+++ b/qutebrowser/completion/models/urlmodel.py
@@ -61,9 +61,9 @@ def url(*, info):
     bookmarks = objreg.get('bookmark-manager').marks.items()
 
     model.add_category(listcategory.ListCategory(
-        'Quickmarks', quickmarks, delete_func=_delete_quickmark))
+        'Quickmarks', quickmarks, delete_func=_delete_quickmark, sort=False))
     model.add_category(listcategory.ListCategory(
-        'Bookmarks', bookmarks, delete_func=_delete_bookmark))
+        'Bookmarks', bookmarks, delete_func=_delete_bookmark, sort=False))
 
     if info.config.get('completion.web_history_max_items') != 0:
         hist_cat = histcategory.HistoryCategory(delete_func=_delete_history)
diff --git a/tests/unit/completion/test_listcategory.py b/tests/unit/completion/test_listcategory.py
index 2ab7defbe..10cde7a60 100644
--- a/tests/unit/completion/test_listcategory.py
+++ b/tests/unit/completion/test_listcategory.py
@@ -24,27 +24,36 @@ import pytest
 from qutebrowser.completion.models import listcategory
 
 
-@pytest.mark.parametrize('pattern, before, after', [
+@pytest.mark.parametrize('pattern, before, after, after_nosort', [
     ('foo',
      [('foo', ''), ('bar', '')],
+     [('foo', '')],
      [('foo', '')]),
 
     ('foo',
      [('foob', ''), ('fooc', ''), ('fooa', '')],
+     [('fooa', ''), ('foob', ''), ('fooc', '')],
      [('foob', ''), ('fooc', ''), ('fooa', '')]),
 
     # prefer foobar as it starts with the pattern
     ('foo',
-     [('barfoo', ''), ('foobar', '')],
-     [('foobar', ''), ('barfoo', '')]),
+     [('barfoo', ''), ('foobaz', ''), ('foobar', '')],
+     [('foobar', ''), ('foobaz', ''), ('barfoo', '')],
+     [('foobaz', ''), ('foobar', ''), ('barfoo', '')]),
 
     ('foo',
      [('foo', 'bar'), ('bar', 'foo'), ('bar', 'bar')],
+     [('foo', 'bar'), ('bar', 'foo')],
      [('foo', 'bar'), ('bar', 'foo')]),
 ])
-def test_set_pattern(pattern, before, after, model_validator):
+def test_set_pattern(pattern, before, after, after_nosort, model_validator):
     """Validate the filtering and sorting results of set_pattern."""
     cat = listcategory.ListCategory('Foo', before)
     model_validator.set_model(cat)
     cat.set_pattern(pattern)
     model_validator.validate(after)
+
+    cat = listcategory.ListCategory('Foo', before, sort=False)
+    model_validator.set_model(cat)
+    cat.set_pattern(pattern)
+    model_validator.validate(after_nosort)
diff --git a/tests/unit/completion/test_models.py b/tests/unit/completion/test_models.py
index 30241b1b3..ca0a54a96 100644
--- a/tests/unit/completion/test_models.py
+++ b/tests/unit/completion/test_models.py
@@ -466,9 +466,9 @@ def test_session_completion(qtmodeltester, session_manager_stub):
     qtmodeltester.check(model)
 
     _check_completions(model, {
-        "Sessions": [('default', None, None),
-                     ('1', None, None),
-                     ('2', None, None)]
+        "Sessions": [('1', None, None),
+                     ('2', None, None),
+                     ('default', None, None)]
     })