[Design][Pluggable Components] History and searching

[nixypanda]

Continuing with the theme of more pluggable components as discussed in #61. I wanted to get thoughts of people of the following History design. This is very close to what we already have and also takes into consideration #55.

Approach

Thinking about the ways we can search history. I could come up with the following ways -

• Going forward/back in history normally
• Going forward/back in history based on a prefix
• Searching for a substring (optionally going forward and backwards)
• Fuzzy search a given string (optionally going forward and backwards)

We can encapsulate this sort of a query into a struct like as follows -

pub enum HistoryNavigationQuery {
    Normal,
    PrefixSearch(String),
    SubstringSearch(String),
    // Suffix Search
    // Fuzzy Search
}

Now keeping this in mind we can have a couple of interfaces we can design for our History.

pub trait History {
    // append any given string (a command) into the history - store
    fn append(&mut self, entry: String) -> ();
    
    // This will set a new navigation setup and based on input query
    fn set_navigation(&mut self, navigation: HistoryNavigationQuery);
    
    // This moves the cursor backwards respecting the navigation query that is set
    // - Results in a no-op if the cursor is at the initial point
    fn back(&mut self);

     // This moves the cursor forwards respecting the navigation-query that is set
    // - Results in a no-op if the cursor is at the latest point
    fn forward(&mut self);
    
    // Returns the string (if present) at the cursor
    fn string_at_cursor(&self) -> Option<String>;
    
    // we will need an `init` method to I guess which Reedline can call to setup the more complicated ones.
}

Some features of this particular design

• We can now have multiple implementors of this like FileBackedHistory, InMemoryHistory, DBBackedHistory, etc.
• We can add any level of intelligence in the implementors as we like as long as they can adhere to this interface.
• All the extensions would be to the type, on the other hand we would have to create more and more functions: like go_back, go_forward, go_back_with_prefix, go_forward_with_prefix, go_back_with_substring, go_back_with_fuzzy, etc
• [Con] We can only have one kind of history navigation at a time in one Reedline process, as we maintain an internal state based on this info. As far as I can see this should be a reasonable assumption to make as a person will only do one kind of search. Well we can circumvent this by using a HashMap to store queries I guess, but I don't think that complication is necessary given that we can assume that there isn't more than one history navigation going on at a given time in one process.

Implementation

Based on whatever the discussion we have here I can start working on this. Though this will conflict heavily with #60. I am not super sure of what the state is there.

[sholderbach]

I generally like the approach using the enum. It would consolidate the stateful part handling indices relative to the current history datastructure. Would from my point of view resolve my gripe in #55.

The peeking list proposed in #60 probably requires would be the ability to peek ahead of the current search cursor i.e. iterator starting there.

I would agree that we currently only require one view into the history.
The question would be if we want to split your proposed trait into two.

• One to handle the appending with implementors responsible for capacity and correct storage.

pub trait History {
    // append any given string (a command) into the history - store
    fn append(&mut self, entry: String) -> ();

}

• A second trait for the browsing. (maybe also containing set_navigation)

pub trait HistoryView {
    // This moves the cursor backwards respecting the navigation query that is set
    // - Results in a no-op if the cursor is at the initial point
    fn back(&mut self);

     // This moves the cursor forwards respecting the navigation-query that is set
    // - Results in a no-op if the cursor is at the latest point
    fn forward(&mut self);
    
    // Returns the string (if present) at the cursor
    fn string_at_cursor(&self) -> Option<String>;
}

Then we could later decide to instead make those stateful searches/browsers independent implementations holding a reference to the datastructure. The implementation for the current proposal could become a larger monolith at some point if all search logic would have to be dispatched based on the enum.

[nixypanda]

I am not sure if I understand this completely. Are you saying that we want to have two separate traits (i.e. History and HistoryView) on the same struct?

Which would look something like the following --

pub struct FilebackedHistory {}

impl History for FileBackedHistory {}

impl HistoryView for FilebackedHistory {}

If this is the case the set_navigation is something we would need. Right? Ideally on the HistoryView. As in there is no way to avoid it.

• I like the segregation of searching trait and the appending to history. 👍
• I am uncertain about the concern that you raised about ---

the implementation for the current proposal could become a larger monolith at some point if all search logic would have to be dispatched based on the enum.

I think the updated proposal that you have offered will also result in the same problem. No?

Or did you mean, that we return HistoryView from the History object itself? I was thinking along these lines too, but I eventually decided that, a solution like that would be quite tricky to get right.

pub trait HistoryNavigationResult {
    fn back(&mut self) -> ();
    fn forward(&mut self) -> ();
    fn string_at_cursor(&self) -> Option<String>;
}

pub trait History {
    fn append(&mut self, entry: String) -> ();
    fn navigate(&self, history_navigation: HistoryNavigationQuery) -> Box<dyn HistoryNavigationResult>;
}

And the implementations for this would look like

pub struct FileBackedHistory {
    entries: VecDeque<String>,
}

// Need to copy over the whole entries stuff in here too.
pub struct FileBackedHistoryNormalResult {}

impl HistoryNavigationResult for FileBackedHistoryNormalResult {}

// Need to copy over the whole entries stuff in here too or a computed version of entries VecDeque
pub struct FileBackedHistoryPrefixSearchResult {}

impl HistoryNavigationResult for FileBackedHistoryPrefixSearchResult {}

impl ImmutableSearchHistory for FileBackedHistory {
   ...
    fn navigate(&mut self, history_navigation: HistoryNavigationQuery) -> Box<dyn HistoryNavigationResult> {
        match history_navigation {
            HistoryNavigationQuery::Normal => Box::new(FileBackedHistoryNormalResult::new()),
            HistoryNavigationQuery::PrefixSearch(_) => Box::new(FileBackedHistoryPrefixSearchResult::new()),
            HistoryNavigationQuery::SubstringSearch(_) => Box::new(FileBackedHistorySubStringSearchResult::new())
        }
    }
}

Here we append to history any new commands that a user will enter. But when the user asks for Navigation Object then we will return a HistoryNavigationResult which has the results of that search, this has the following features I can think of

• Will result in neatly organised SearchResult struct which will not turn monolithic
• [con] Reedline will need to store this SearchResult struct in it.
• [con] Will also need to update this object every time there is a new append to the history.

in addition to this there are a bunch of other questions that we will need to answer.

• do we share the object that is storing the history commands? I am not sure how the borrowing etc, rules will work in this particular case. Also, the lifetime rules would be tricky to manage (given that lifetime of any of the implementors for HistoryNavigationReuslt will be less than that of the one implementing History. Other questions like what happens if this is alive and we append more stuff etc, can be ignored given that when the search is active there is no appending etc happening
• Another approach that I can think of is using immutable structures. Now I am not sure how good is support for such stuff in rust but if it works something like what we have in haskell, or immutable-js then it should be super easy as we can cheaply copy over the entries into the search result without having to think about lifetime etc.

considering all this I decided that maybe bloating up the match block that operates on the enum is probably the better choice as it is significantly simpler to deal with than this.

or did you you mean something else entirely?

[sholderbach]

Your proposed API is certainly easier to implement for now and allows to incorporate in a modal/configurable fashion to run different search/navigation strategies. With the addition of a method peek_elements(&self, n: usize) -> impl Iterator or -> &[String] to grab a bunch of elements starting at the current history entry the list display in #60 would be easily feasible.

My thought of those View structs was, that they hold during their lifetime (invalid during appending) a immutable reference to a slice or iterator of the history (handed out by the History trait implementor). But yes this certainly runs into an invalidation problem. Also one could imagine a history implementation that wants to pull in global changes to the history and would not register new entries in a different window.

[nixypanda]

@sholderbach Have you looked into https://github.com/bodil/im-rs, I skimmed through the docs and this will probably help us avoid all the invalidation issues as we will send out a copy to the View objects. Also, this will not hit performance much as behind the scenes there would be structural sharing.

Let me know your thoughts on this and I can work on the approach that we agree on.