Understanding atuin history search

ellie · June 25, 2024, 9:02pm

Thanks for bringing this up! It’s currently sorting by minspan, which can sometimes feel wrong depending on the query. I’ve been wanting to improve on it for a while, but doing so without regressions, including performance impact is harder than I’d like.

It’ll probably be because

curl http://shop-data-s-4vcpu-16gb-320gb-intel-nyc3-0b

isn’t actually that bad by that scoring, but obviously looks wrong to a user. We’re not doing any tokenisation either, so cannot prioritise terms properly, which makes that harder.

First, our minspan sorting is here;

github.com

atuinsh/atuin/blob/fd3aca7cb3394d895d27e8cea26a02948b06d6f1/crates/atuin-client/src/ordering.rs

use minspan::minspan;

use super::{history::History, settings::SearchMode};

pub fn reorder_fuzzy(mode: SearchMode, query: &str, res: Vec<History>) -> Vec<History> {
    match mode {
        SearchMode::Fuzzy => reorder(query, |x| &x.command, res),
        _ => res,
    }
}

fn reorder<F, A>(query: &str, f: F, res: Vec<A>) -> Vec<A>
where
    F: Fn(&A) -> &String,
    A: Clone,
{
    let mut r = res.clone();
    let qvec = &query.chars().collect();
    r.sort_by_cached_key(|h| {
        // TODO for fzf search we should sum up scores for each matched term

This file has been truncated. show original

We’ve also experimented with Skim (similar to fzf, but usable as a library). The issue there is that the startup time is noticeable to users, as we need to read and index all shell history (same issues with atuin list | fzf)

I’d like to make some changes really, but doing so without a set of examples of what most people think feels good is tricky. There’s an initial attempt at that hiding behind

smart_sort = true

In config. Implementation here:

github.com

atuinsh/atuin/blob/main/crates/atuin/src/command/client/search/sort.rs

use atuin_client::history::History;

type ScoredHistory = (f64, History);

// Fuzzy search already comes sorted by minspan
// This sorting should be applicable to all search modes, and solve the more "obvious" issues
// first.
// Later on, we can pass in context and do some boosts there too.
pub fn sort(query: &str, input: Vec<History>) -> Vec<History> {
    // This can totally be extended. We need to be _careful_ that it's not slow.
    // We also need to balance sorting db-side with sorting here. SQLite can do a lot,
    // but some things are just much easier/more doable in Rust.

    let mut scored = input
        .into_iter()
        .map(|h| {
            // If history is _prefixed_ with the query, score it more highly
            let score = if h.command.starts_with(query) {
                2.0
            } else if h.command.contains(query) {

This file has been truncated. show original

It’ll basically prefer newer commands, and commands that more literally contain the query. If you give it a go and lmk how it works for you, that would be great!

The other limitations are because we’re trying to approximate fzf in sql, which doesn’t work as well as I’d like (implementation here)

Otherwise, some other search modes may feel better to you: Config | Atuin Docs

Maybe more detail than you wanted, but I’m very happy to discuss further