History pager to fall back to subsequence search

[elebow]

Description

This adds a subsequence search type to the history command. It was easier than I expected because wcstringutil already had a subsequence_in_string()!

#1874 discussed adding this behavior to history-pager, but history seemed easier so I figured it was better to start with this. We can do history-pager in a followup PR, or add it to this one.

TODOs:

• Changes to fish usage are reflected in user documentation/manpages.
• Tests have been added for regressions fixed
• User-visible changes noted in CHANGELOG.rst

[elebow]

I also wonder if it is reasonable to replace contains with subsequence, since the latter is a superset.

[krobelus]

I also wonder if it is reasonable to replace contains with subsequence, since the latter is a superset.

when a user expects the contains-check, subsequence semantics would give false positives

[krobelus]

I don't think it is very useful to expose this.
I think we should instead document that the default search type (--contains) uses glob matching, so we can use this today:

history search --contains 'e*c* *h*e*a*g'

or, more realistically

history search --contains 'ec*he*ag'

We can do history-pager in a followup PR, or add it to this one.

That sounds exciting

[elebow]

I removed the --prefix argument and used the fallback logic described at #1874 (comment).

Unfortunately, I was unable to get either history or history-pager to work as desired.

[elebow]

I don't know how to check whether there were no results. history_t::search seems to write directly to an IO stream, and returns false only when the user supplies invalid arguments.

[krobelus]

it's easier if we move this logic further down the call stack:

diff --git a/src/history.cpp b/src/history.cpp
index c07a7ebb9..e8a7d7913 100644
--- a/src/history.cpp
+++ b/src/history.cpp
@@ -1475,9 +1475,16 @@ static void do_1_history_search(history_t *hist, history_search_type_t search_ty
     history_search_t searcher = history_search_t(hist, search_string, search_type,
                                                  case_sensitive ? 0 : history_search_ignore_case);
+    bool success = false;
     while (!cancel_check() && searcher.go_to_next_match(history_search_direction_t::backward)) {
+        success = true;
         if (!func(searcher.current_item())) {
             break;
         }
     }
+    if (!success && (search_type == history_search_type_t::contains ||
+                     search_type == history_search_type_t::contains_glob)) {
+        do_1_history_search(hist, history_search_type_t::contains_subsequence, search_string,
+                            case_sensitive, func, cancel_check);
+    }
 }
 

[elebow]

go_to_next_match seems to return true even when there are no matches. I don't know else to determine whether there were no matches.

[krobelus]

With this small tweak, it seems to work fine for me.
The problem was that the fallback search goes out of scope, so it would always use the substring search.

diff --git a/src/reader.cpp b/src/reader.cpp
index a3b54126d..174b48cd5 100644
--- a/src/reader.cpp
+++ b/src/reader.cpp
@@ -1327,10 +1327,10 @@ static history_pager_result_t history_pager_search(const std::shared_ptr<history
     bool next_match_found = search.go_to_next_match(direction);
     if (!next_match_found) {
         // If there were no matches, try again with subsequence search
-        history_search_t search{history, search_string, history_search_type_t::contains_subsequence,
-                                smartcase_flags(search_string), history_index};
+        search =
+            history_search_t{history, search_string, history_search_type_t::contains_subsequence,
+                             smartcase_flags(search_string), history_index};
         next_match_found = search.go_to_next_match(direction);
-        // TODO next_match_found is 1 even if there are no matches
     }
     while (completions.size() < page_size && next_match_found) {
         const history_item_t &item = search.current_item();

[elebow]

This was another attempt to check for no matches, but it doesn't seem to be useful because current_item is null before go_to_next_match() is called, even if there are matches.

[krobelus]

current_item is only set after the first go_to_next_match()

[elebow]

Thanks for the tips. I think this PR is now working as intended.

However, I have been using this locally and I think I prefer it: master...elebow:fish-shell:history-contains-and-subsequence-search

I believe it offers a few advantages:

1. Keeping history --contains and history --subsequence separate allows a user to choose which search they want. With the behavior in this PR, there is no way to do only a substring search.

   I haven't personally used history yet (as a new fish user), so I don't know if this is important. But since history already offers other search methods (--prefix, --exact), it makes sense to keep --contains and --subsequence separate. Though maybe not with those names (--contains → --substring perhaps?).

2. I prefer the behavior of history-pager to include all subsequence matches, even if a substring match exists. It just seems easier to use, to me.

If the approach in this PR is accepted as the default behavior, I would at least want a configuration variable or alternative input command (history-pager-subsequence maybe) for the alternative behavior.

[Edit: This comment previously suggested elebow/fish-shell@master...elebow:fish-shell:history-subsequence-search-alternative, but after using that for a few days, I no longer like it.]

[elebow]

I've been mulling the idea of making history-pager into a more generic selection-pager that just takes an iterator and shows the selection/paging UI.

Then a history pager could be accomplished with something like:

history | selection-pager

Or if a user wanted to start with the oldest entry:

history | sort -r | selection-pager

Or any other arbitrary list could be passed in (file glob, git branches, ...)

And with selection-pager as its own input function, it makes more sense to allow multiple search strategies:

history | selection-pager-prefix
history | selection-pager-subsequence

---

I understand that there is some complication in combining input functions and normal commands, but it might be surmountable (with commandline -f?). I'm still new to fish and haven't explored this idea much yet.

[krobelus]

I like the change to the history pager a lot, I think it's a strict improvement.
(Sadly when building fish in debug mode, it can be quite laggy on a large history but that's no big deal)

We should probably also add the fallback behavior to up-arrow search... though I'm not 100% sure, we can leave that for later.

I don't think we should change the history builtin.
As mentioned above, the equivalent behavior can already achieved with globs (the extra keystrokes are no big deal unlike in the interactive search).
Additionally, the behavior change could break existing scripts.

If the approach in this PR is accepted as the default behavior, I would at least want a configuration variable or alternative input command (history-pager-subsequence maybe) for the alternative behavior.

preferrably history-pager is good enough for everyone but if it's just one extra special input function history-pager-subsequence, we can probably add that. I don't expect anyone wants a "prefix" variant. We might want a history-pager-token one though (I think the fzf integration offers something similar).

1. I prefer the behavior of history-pager to include all subsequence matches, even if a substring match exists. It just seems easier to use, to me.

I see. I like the tiered behavior because it gives better results when typing an exact substring, which users are already used to doing.
The completion pager has the same behavior (see completion_t::rank()).
In future we should teach the interactive history searches to factor in the smartcase match-type like that function does.

history | selection-pager

This would lack history-specific stuff like syntax highlighting and future features like the ability to delete the selected history items or a timestamp in the description.

Or any other arbitrary list could be passed in (file glob, git branches, ...)

for generic menus, fzf should work well

[elebow]

Okay, I've removed the changes to the history builtin.

The tiered behavior is in this PR, and the "always include everything" behavior is in master...elebow:fish-shell:history-contains-and-subsequence-search. Maybe in a future PR we can add a second history-pager-subsequence, or a fish_ configuration variable.

[krobelus]

I like the new behavior, maybe we should add it to a patch release

[cklim24]

Description

This adds a subsequence search type to the history command. It was easier than I expected because wcstringutil already had a subsequence_in_string()!

#1874 discussed adding this behavior to history-pager, but history seemed easier so I figured it was better to start with this. We can do history-pager in a followup PR, or add it to this one.

TODOs:

• Changes to fish usage are reflected in user documentation/manpages.
• Tests have been added for regressions fixed
• User-visible changes noted in CHANGELOG.rst