ranked match: prefer input order over alphabetical order for user-specified completions

When using either of

	set-option g completers option=my_option
	prompt -shell-script-candidates ...

While the search text is empty, the completions will be sorted
alphabetically.
This is bad because it means the most important entries are not listed
first, making them harder to select or even spot.

Let's apply input order before resorting to sorting alphabetically.

In theory there is a more elegant solution: sort candidates (except
if they're user input) before passing them to RankedMatch, and then
always use stable sort. However that doesn't work because we use a
heap which doesn't support stable sort.

Closes #1709, #4813

4 files changed, 12 insertions, 2 deletions

diff --git a/src/commands.cc b/src/commands.cc
index 5c3b5f39..3413d095 100644
--- a/src/commands.cc
+++ b/src/commands.cc
@@ -337,10 +337,13 @@ private:
     {
         UsedLetters query_letters = used_letters(query);
         Vector<RankedMatch> matches;
-        for (auto&& candidate : m_candidates)
+        for (auto&& [i, candidate] : m_candidates | enumerate())
         {
             if (RankedMatch m{candidate.first, candidate.second, query, query_letters})
+            {
+                m.set_input_sequence_number(i);
                 matches.push_back(m);
+            }
         }
 
         constexpr size_t max_count = 100;
diff --git a/src/insert_completer.cc b/src/insert_completer.cc
index c43d9761..af387506 100644
--- a/src/insert_completer.cc
+++ b/src/insert_completer.cc
@@ -298,10 +298,11 @@ InsertCompletion complete_option(const SelectionList& sels,
     StringView query = buffer.substr(coord, cursor_pos);
     Vector<RankedMatchAndInfo> matches;
 
-    for (auto& candidate : opt.list)
+    for (auto&& [i, candidate] : opt.list | enumerate())
     {
         if (RankedMatchAndInfo match{std::get<0>(candidate), query})
         {
+            match.set_input_sequence_number(i);
             match.on_select = std::get<1>(candidate);
             auto& menu = std::get<2>(candidate);
             match.menu_entry = not menu.empty() ?
diff --git a/src/ranked_match.cc b/src/ranked_match.cc
index 2abea8d9..77cf758d 100644
--- a/src/ranked_match.cc
+++ b/src/ranked_match.cc
@@ -208,6 +208,9 @@ bool RankedMatch::operator<(const RankedMatch& other) const
     if (m_max_index != other.m_max_index)
         return m_max_index < other.m_max_index;
 
+    if (m_input_sequence_number != other.m_input_sequence_number)
+        return m_input_sequence_number < other.m_input_sequence_number;
+
     // Reorder codepoints to improve matching behaviour
     auto order = [](Codepoint cp) { return cp == '/' ? 0 : cp; };
 
diff --git a/src/ranked_match.hh b/src/ranked_match.hh
index 01afe9cd..5a58defb 100644
--- a/src/ranked_match.hh
+++ b/src/ranked_match.hh
@@ -31,6 +31,8 @@ struct RankedMatch
 
     explicit operator bool() const { return m_matches; }
 
+    void set_input_sequence_number(size_t i) { m_input_sequence_number = i; }
+
 private:
     template<typename TestFunc>
     RankedMatch(StringView candidate, StringView query, TestFunc test);
@@ -54,6 +56,7 @@ private:
     Flags m_flags = Flags::None;
     int m_word_boundary_match_count = 0;
     int m_max_index = 0;
+    size_t m_input_sequence_number = 0;
 };
 
 }