From bb7f00dbef3bf4c7c00c1969cb0089de51bd9ba9 Mon Sep 17 00:00:00 2001 From: Conrad Ludgate Date: Sun, 26 Mar 2023 15:47:38 +0100 Subject: chore: use fork of skim (#803) * use fuzzy-matcher instead of skim switch to a search-engine abstraction * fmt * fix deprecated warnings --- src/command/client.rs | 2 +- src/command/client/search.rs | 8 +- src/command/client/search/engines.rs | 46 ++++++++++ src/command/client/search/engines/db.rs | 30 +++++++ src/command/client/search/engines/skim.rs | 145 ++++++++++++++++++++++++++++++ src/command/client/search/history_list.rs | 8 +- src/command/client/search/interactive.rs | 128 +++++++------------------- src/command/client/search/skim_impl.rs | 92 ------------------- 8 files changed, 260 insertions(+), 199 deletions(-) create mode 100644 src/command/client/search/engines.rs create mode 100644 src/command/client/search/engines/db.rs create mode 100644 src/command/client/search/engines/skim.rs delete mode 100644 src/command/client/search/skim_impl.rs (limited to 'src') diff --git a/src/command/client.rs b/src/command/client.rs index 551b2225..2a825638 100644 --- a/src/command/client.rs +++ b/src/command/client.rs @@ -53,7 +53,7 @@ impl Cmd { Self::History(history) => history.run(&settings, &mut db).await, Self::Import(import) => import.run(&mut db).await, Self::Stats(stats) => stats.run(&mut db, &settings).await, - Self::Search(search) => search.run(&mut db, &mut settings).await, + Self::Search(search) => search.run(db, &mut settings).await, #[cfg(feature = "sync")] Self::Sync(sync) => sync.run(settings, &mut db).await, } diff --git a/src/command/client/search.rs b/src/command/client/search.rs index 50dfec10..c407eb08 100644 --- a/src/command/client/search.rs +++ b/src/command/client/search.rs @@ -14,9 +14,9 @@ use super::history::ListMode; mod cursor; mod duration; +mod engines; mod history_list; mod interactive; -mod skim_impl; pub use duration::{format_duration, format_duration_into}; #[allow(clippy::struct_excessive_bools)] @@ -87,7 +87,7 @@ pub struct Cmd { } impl Cmd { - pub async fn run(self, db: &mut impl Database, settings: &mut Settings) -> Result<()> { + pub async fn run(self, mut db: impl Database, settings: &mut Settings) -> Result<()> { if self.search_mode.is_some() { settings.search_mode = self.search_mode.unwrap(); } @@ -113,7 +113,7 @@ impl Cmd { self.after.clone(), self.limit, &self.query, - db, + &mut db, ) .await?; @@ -142,7 +142,7 @@ impl Cmd { self.after.clone(), self.limit, &self.query, - db, + &mut db, ) .await?; } diff --git a/src/command/client/search/engines.rs b/src/command/client/search/engines.rs new file mode 100644 index 00000000..878b1431 --- /dev/null +++ b/src/command/client/search/engines.rs @@ -0,0 +1,46 @@ +use async_trait::async_trait; +use atuin_client::{ + database::{Context, Database}, + history::History, + settings::{FilterMode, SearchMode}, +}; +use eyre::Result; + +use super::cursor::Cursor; + +pub mod db; +pub mod skim; + +pub fn engine(search_mode: SearchMode) -> Box { + match search_mode { + SearchMode::Skim => Box::new(skim::Search::new()) as Box<_>, + mode => Box::new(db::Search(mode)) as Box<_>, + } +} + +pub struct SearchState { + pub input: Cursor, + pub filter_mode: FilterMode, + pub context: Context, +} + +#[async_trait] +pub trait SearchEngine: Send + Sync + 'static { + async fn full_query( + &mut self, + state: &SearchState, + db: &mut dyn Database, + ) -> Result>; + + async fn query(&mut self, state: &SearchState, db: &mut dyn Database) -> Result> { + if state.input.as_str().is_empty() { + Ok(db + .list(state.filter_mode, &state.context, Some(200), true) + .await? + .into_iter() + .collect::>()) + } else { + self.full_query(state, db).await + } + } +} diff --git a/src/command/client/search/engines/db.rs b/src/command/client/search/engines/db.rs new file mode 100644 index 00000000..5a35da10 --- /dev/null +++ b/src/command/client/search/engines/db.rs @@ -0,0 +1,30 @@ +use async_trait::async_trait; +use atuin_client::{database::Database, history::History, settings::SearchMode}; +use eyre::Result; + +use super::{SearchEngine, SearchState}; + +pub struct Search(pub SearchMode); + +#[async_trait] +impl SearchEngine for Search { + async fn full_query( + &mut self, + state: &SearchState, + db: &mut dyn Database, + ) -> Result> { + Ok(db + .search( + self.0, + state.filter_mode, + &state.context, + state.input.as_str(), + Some(200), + None, + None, + ) + .await? + .into_iter() + .collect::>()) + } +} diff --git a/src/command/client/search/engines/skim.rs b/src/command/client/search/engines/skim.rs new file mode 100644 index 00000000..76049312 --- /dev/null +++ b/src/command/client/search/engines/skim.rs @@ -0,0 +1,145 @@ +use std::path::Path; + +use async_trait::async_trait; +use atuin_client::{database::Database, history::History, settings::FilterMode}; +use chrono::Utc; +use eyre::Result; +use fuzzy_matcher::{skim::SkimMatcherV2, FuzzyMatcher}; +use tokio::task::yield_now; + +use super::{SearchEngine, SearchState}; + +pub struct Search { + all_history: Vec<(History, i32)>, + engine: SkimMatcherV2, +} + +impl Search { + pub fn new() -> Self { + Search { + all_history: vec![], + engine: SkimMatcherV2::default(), + } + } +} + +#[async_trait] +impl SearchEngine for Search { + async fn full_query( + &mut self, + state: &SearchState, + db: &mut dyn Database, + ) -> Result> { + if self.all_history.is_empty() { + self.all_history = db.all_with_count().await.unwrap(); + } + + Ok(fuzzy_search(&self.engine, state, &self.all_history).await) + } +} + +async fn fuzzy_search( + engine: &SkimMatcherV2, + state: &SearchState, + all_history: &[(History, i32)], +) -> Vec { + let mut set = Vec::with_capacity(200); + let mut ranks = Vec::with_capacity(200); + let query = state.input.as_str(); + let now = Utc::now(); + + for (i, (history, count)) in all_history.iter().enumerate() { + if i % 256 == 0 { + yield_now().await; + } + match state.filter_mode { + FilterMode::Global => {} + FilterMode::Host if history.hostname == state.context.hostname => {} + FilterMode::Session if history.session == state.context.session => {} + FilterMode::Directory if history.cwd == state.context.cwd => {} + _ => continue, + } + #[allow(clippy::cast_lossless, clippy::cast_precision_loss)] + if let Some((score, indices)) = engine.fuzzy_indices(&history.command, query) { + let begin = indices.first().copied().unwrap_or_default(); + + let mut duration = ((now - history.timestamp).num_seconds() as f64).log2(); + if !duration.is_finite() || duration <= 1.0 { + duration = 1.0; + } + // these + X.0 just make the log result a bit smoother. + // log is very spiky towards 1-4, but I want a gradual decay. + // eg: + // log2(4) = 2, log2(5) = 2.3 (16% increase) + // log2(8) = 3, log2(9) = 3.16 (5% increase) + // log2(16) = 4, log2(17) = 4.08 (2% increase) + let count = (*count as f64 + 8.0).log2(); + let begin = (begin as f64 + 16.0).log2(); + let path = path_dist(history.cwd.as_ref(), state.context.cwd.as_ref()); + let path = (path as f64 + 8.0).log2(); + + // reduce longer durations, raise higher counts, raise matches close to the start + let score = (-score as f64) * count / path / duration / begin; + + 'insert: { + // algorithm: + // 1. find either the position that this command ranks + // 2. find the same command positioned better than our rank. + for i in 0..set.len() { + // do we out score the corrent position? + if ranks[i] > score { + ranks.insert(i, score); + set.insert(i, history.clone()); + let mut j = i + 1; + while j < set.len() { + // remove duplicates that have a worse score + if set[j].command == history.command { + ranks.remove(j); + set.remove(j); + + // break this while loop because there won't be any other + // duplicates. + break; + } + j += 1; + } + + // keep it limited + if ranks.len() > 200 { + ranks.pop(); + set.pop(); + } + + break 'insert; + } + // don't continue if this command has a better score already + if set[i].command == history.command { + break 'insert; + } + } + + if set.len() < 200 { + ranks.push(score); + set.push(history.clone()); + } + } + } + } + + set +} + +fn path_dist(a: &Path, b: &Path) -> usize { + let mut a: Vec<_> = a.components().collect(); + let b: Vec<_> = b.components().collect(); + + let mut dist = 0; + + // pop a until there's a common anscestor + while !b.starts_with(&a) { + dist += 1; + a.pop(); + } + + b.len() - a.len() + dist +} diff --git a/src/command/client/search/history_list.rs b/src/command/client/search/history_list.rs index 60ec15a8..928fe4c7 100644 --- a/src/command/client/search/history_list.rs +++ b/src/command/client/search/history_list.rs @@ -1,4 +1,4 @@ -use std::{sync::Arc, time::Duration}; +use std::time::Duration; use atuin_client::history::History; use ratatui::{ @@ -8,10 +8,10 @@ use ratatui::{ widgets::{Block, StatefulWidget, Widget}, }; -use super::{format_duration, interactive::HistoryWrapper}; +use super::format_duration; pub struct HistoryList<'a> { - history: &'a [Arc], + history: &'a [History], block: Option>, } @@ -77,7 +77,7 @@ impl<'a> StatefulWidget for HistoryList<'a> { } impl<'a> HistoryList<'a> { - pub fn new(history: &'a [Arc]) -> Self { + pub fn new(history: &'a [History]) -> Self { Self { history, block: None, diff --git a/src/command/client/search/interactive.rs b/src/command/client/search/interactive.rs index 6fd4e1d8..a7ee9bae 100644 --- a/src/command/client/search/interactive.rs +++ b/src/command/client/search/interactive.rs @@ -1,7 +1,5 @@ use std::{ io::{stdout, Write}, - ops::Deref, - sync::Arc, time::Duration, }; @@ -12,21 +10,21 @@ use crossterm::{ use eyre::Result; use futures_util::FutureExt; use semver::Version; -use skim::SkimItem; use unicode_width::UnicodeWidthStr; use atuin_client::{ + database::current_context, database::Database, - database::{current_context, Context}, history::History, settings::{ExitMode, FilterMode, SearchMode, Settings}, }; use super::{ cursor::Cursor, + engines::{SearchEngine, SearchState}, history_list::{HistoryList, ListState, PREFIX_LENGTH}, }; -use crate::VERSION; +use crate::{command::client::search::engines, VERSION}; use ratatui::{ backend::{Backend, CrosstermBackend}, layout::{Alignment, Constraint, Direction, Layout}, @@ -43,68 +41,16 @@ struct State { history_count: i64, update_needed: Option, results_state: ListState, - search: SearchState, - - // only allocated if using skim - all_history: Vec>, -} - -pub struct SearchState { - pub input: Cursor, - pub filter_mode: FilterMode, - pub search_mode: SearchMode, - /// Store if the user has _just_ changed the search mode. - /// If so, we change the UI to show the search mode instead - /// of the filter mode until user starts typing again. switched_search_mode: bool, - pub context: Context, + search_mode: SearchMode, + + search: SearchState, + engine: Box, } impl State { - async fn query_results(&mut self, db: &mut impl Database) -> Result>> { - let i = self.search.input.as_str(); - let results = if i.is_empty() { - db.list( - self.search.filter_mode, - &self.search.context, - Some(200), - true, - ) - .await? - .into_iter() - .map(|history| HistoryWrapper { history, count: 1 }) - .map(Arc::new) - .collect::>() - } else if self.search.search_mode == SearchMode::Skim { - if self.all_history.is_empty() { - self.all_history = db - .all_with_count() - .await - .unwrap() - .into_iter() - .map(|(history, count)| HistoryWrapper { history, count }) - .map(Arc::new) - .collect::>(); - } - - super::skim_impl::fuzzy_search(&self.search, &self.all_history).await - } else { - db.search( - self.search.search_mode, - self.search.filter_mode, - &self.search.context, - i, - Some(200), - None, - None, - ) - .await? - .into_iter() - .map(|history| HistoryWrapper { history, count: 1 }) - .map(Arc::new) - .collect::>() - }; - + async fn query_results(&mut self, db: &mut dyn Database) -> Result> { + let results = self.engine.query(&self.search, db).await?; self.results_state.select(0); Ok(results) } @@ -154,7 +100,7 @@ impl State { let ctrl = input.modifiers.contains(KeyModifiers::CONTROL); let alt = input.modifiers.contains(KeyModifiers::ALT); // reset the state, will be set to true later if user really did change it - self.search.switched_search_mode = false; + self.switched_search_mode = false; match input.code { KeyCode::Char('c' | 'd' | 'g') if ctrl => return Some(RETURN_ORIGINAL), KeyCode::Esc => { @@ -228,8 +174,9 @@ impl State { self.search.filter_mode = FILTER_MODES[i]; } KeyCode::Char('s') if ctrl => { - self.search.switched_search_mode = true; - self.search.search_mode = self.search.search_mode.next(settings); + self.switched_search_mode = true; + self.search_mode = self.search_mode.next(settings); + self.engine = engines::engine(self.search_mode); } KeyCode::Down if self.results_state.selected() == 0 => { return Some(match settings.exit_mode { @@ -275,7 +222,7 @@ impl State { fn draw( &mut self, f: &mut Frame<'_, T>, - results: &[Arc], + results: &[History], compact: bool, show_preview: bool, ) { @@ -391,7 +338,7 @@ impl State { stats } - fn build_results_list(compact: bool, results: &[Arc]) -> HistoryList { + fn build_results_list(compact: bool, results: &[History]) -> HistoryList { let results_list = if compact { HistoryList::new(results) } else { @@ -407,8 +354,8 @@ impl State { fn build_input(&mut self, compact: bool, chunk_width: usize) -> Paragraph { /// Max width of the UI box showing current mode const MAX_WIDTH: usize = 14; - let (pref, mode) = if self.search.switched_search_mode { - (" SRCH:", self.search.search_mode.as_str()) + let (pref, mode) = if self.switched_search_mode { + (" SRCH:", self.search_mode.as_str()) } else { ("", self.search.filter_mode.as_str()) }; @@ -431,7 +378,7 @@ impl State { fn build_preview( &mut self, - results: &[Arc], + results: &[History], compact: bool, preview_width: u16, chunk_width: usize, @@ -513,23 +460,6 @@ impl Write for Stdout { } } -pub struct HistoryWrapper { - history: History, - pub count: i32, -} -impl Deref for HistoryWrapper { - type Target = History; - - fn deref(&self) -> &Self::Target { - &self.history - } -} -impl SkimItem for HistoryWrapper { - fn text(&self) -> std::borrow::Cow { - std::borrow::Cow::Borrowed(self.history.command.as_str()) - } -} - // this is a big blob of horrible! clean it up! // for now, it works. But it'd be great if it were more easily readable, and // modular. I'd like to add some more stats and stuff at some point @@ -537,7 +467,7 @@ impl SkimItem for HistoryWrapper { pub async fn history( query: &[String], settings: &Settings, - db: &mut impl Database, + mut db: impl Database, ) -> Result { let stdout = Stdout::new(settings.inline_height > 0)?; let backend = CrosstermBackend::new(stdout); @@ -562,10 +492,14 @@ pub async fn history( let context = current_context(); + let history_count = db.history_count().await?; + let mut app = State { - history_count: db.history_count().await?, + history_count, results_state: ListState::default(), update_needed: None, + switched_search_mode: false, + search_mode: settings.search_mode, search: SearchState { input, context, @@ -576,13 +510,11 @@ pub async fn history( } else { settings.filter_mode }, - search_mode: settings.search_mode, - switched_search_mode: false, }, - all_history: Vec::new(), + engine: engines::engine(settings.search_mode), }; - let mut results = app.query_results(db).await?; + let mut results = app.query_results(&mut db).await?; let index = 'render: loop { let compact = match settings.style { @@ -596,7 +528,7 @@ pub async fn history( let initial_input = app.search.input.as_str().to_owned(); let initial_filter_mode = app.search.filter_mode; - let initial_search_mode = app.search.search_mode; + let initial_search_mode = app.search_mode; let event_ready = tokio::task::spawn_blocking(|| event::poll(Duration::from_millis(250))); @@ -620,9 +552,9 @@ pub async fn history( if initial_input != app.search.input.as_str() || initial_filter_mode != app.search.filter_mode - || initial_search_mode != app.search.search_mode + || initial_search_mode != app.search_mode { - results = app.query_results(db).await?; + results = app.query_results(&mut db).await?; } }; @@ -632,7 +564,7 @@ pub async fn history( if index < results.len() { // index is in bounds so we return that entry - Ok(results.swap_remove(index).command.clone()) + Ok(results.swap_remove(index).command) } else if index == RETURN_ORIGINAL { Ok(String::new()) } else { diff --git a/src/command/client/search/skim_impl.rs b/src/command/client/search/skim_impl.rs deleted file mode 100644 index 416d0e46..00000000 --- a/src/command/client/search/skim_impl.rs +++ /dev/null @@ -1,92 +0,0 @@ -use std::sync::Arc; - -use atuin_client::settings::FilterMode; -use chrono::Utc; -use skim::{prelude::ExactOrFuzzyEngineFactory, MatchEngineFactory}; -use tokio::task::yield_now; - -use super::interactive::{HistoryWrapper, SearchState}; - -pub async fn fuzzy_search( - state: &SearchState, - all_history: &[Arc], -) -> Vec> { - let mut set = Vec::with_capacity(200); - let mut ranks = Vec::with_capacity(200); - let engine = ExactOrFuzzyEngineFactory::builder().fuzzy_algorithm(skim::FuzzyAlgorithm::SkimV2); - let query = state.input.as_str(); - let engine = engine.create_engine(query); - let now = Utc::now(); - - for (i, item) in all_history.iter().enumerate() { - if i % 256 == 0 { - yield_now().await; - } - match state.filter_mode { - FilterMode::Global => {} - FilterMode::Host if item.hostname == state.context.hostname => {} - FilterMode::Session if item.session == state.context.session => {} - FilterMode::Directory if item.cwd == state.context.cwd => {} - _ => continue, - } - #[allow(clippy::cast_lossless, clippy::cast_precision_loss)] - if let Some(res) = engine.match_item(item.clone()) { - let [score, begin, _, _] = res.rank; - - let mut duration = ((now - item.timestamp).num_seconds() as f64).log2(); - if !duration.is_finite() || duration <= 1.0 { - duration = 1.0; - } - let count = (item.count as f64 + 16.0).log2(); - let begin = (begin as f64 + 16.0).log2(); - - // reduce longer durations, raise higher counts, raise matches close to the start - let score = (score as f64) * count / duration / begin; - - 'insert: { - // algorithm: - // 1. find either the position that this command ranks - // 2. find the same command positioned better than our rank. - for i in 0..set.len() { - // do we out score the corrent position? - if ranks[i] > score { - ranks.insert(i, score); - set.insert(i, item.clone()); - let mut j = i + 1; - while j < set.len() { - // remove duplicates that have a worse score - if set[j].command == item.command { - ranks.remove(j); - set.remove(j); - - // break this while loop because there won't be any other - // duplicates. - break; - } - j += 1; - } - - // keep it limited - if ranks.len() > 200 { - ranks.pop(); - set.pop(); - } - - break 'insert; - } - // don't continue if this command has a better score already - if set[i].command == item.command { - break 'insert; - } - } - - if set.len() < 200 { - ranks.push(score); - set.push(item.clone()); - } - } - } - } - - set -} -- cgit v1.3.1