skim-demo (#695)

* skim-demo

* skim some more

* Weight first word match higher (#712)

* some improvements

* make skim opt-in

---------

Co-authored-by: Frank Hamand <frankhamand@gmail.com>

8 files changed, 595 insertions, 72 deletions

diff --git a/Cargo.lock b/Cargo.lock
index c4f0c8c29..2e75c2dc3 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -38,6 +38,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "b9a8f622bcf6ff3df478e9deba3e03e4e04b300f8e6a139e192c05fa3490afc7"
 
 [[package]]
+name = "arrayvec"
+version = "0.7.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8da52d66c7071e2e3fa2a1e5c6d088fec47b593032b254f5e980de8ea54454d6"
+
+[[package]]
 name = "async-trait"
 version = "0.1.58"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -98,6 +104,7 @@ dependencies = [
  "semver",
  "serde",
  "serde_json",
+ "skim",
  "tiny-bip39",
  "tokio",
  "tracing-subscriber",
@@ -324,7 +331,7 @@ dependencies = [
  "num-integer",
  "num-traits",
  "serde",
- "time",
+ "time 0.1.44",
  "wasm-bindgen",
  "winapi",
 ]
@@ -453,6 +460,20 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "2d0165d2900ae6778e36e80bbc4da3b5eefccee9ba939761f9c2882a5d9af3ff"
 
 [[package]]
+name = "crossbeam"
+version = "0.8.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2801af0d36612ae591caa9568261fddce32ce6e08a7275ea334a06a4ad021a2c"
+dependencies = [
+ "cfg-if",
+ "crossbeam-channel",
+ "crossbeam-deque",
+ "crossbeam-epoch",
+ "crossbeam-queue",
+ "crossbeam-utils",
+]
+
+[[package]]
 name = "crossbeam-channel"
 version = "0.5.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -463,6 +484,30 @@ dependencies = [
 ]
 
 [[package]]
+name = "crossbeam-deque"
+version = "0.8.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "715e8152b692bba2d374b53d4875445368fdf21a94751410af607a5ac677d1fc"
+dependencies = [
+ "cfg-if",
+ "crossbeam-epoch",
+ "crossbeam-utils",
+]
+
+[[package]]
+name = "crossbeam-epoch"
+version = "0.9.13"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "01a9af1f4c2ef74bb8aa1f7e19706bc72d03598c8a570bb5de72243c7a9d9d5a"
+dependencies = [
+ "autocfg",
+ "cfg-if",
+ "crossbeam-utils",
+ "memoffset 0.7.1",
+ "scopeguard",
+]
+
+[[package]]
 name = "crossbeam-queue"
 version = "0.3.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -519,6 +564,82 @@ dependencies = [
 ]
 
 [[package]]
+name = "darling"
+version = "0.14.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b0dd3cd20dc6b5a876612a6e5accfe7f3dd883db6d07acfbf14c128f61550dfa"
+dependencies = [
+ "darling_core",
+ "darling_macro",
+]
+
+[[package]]
+name = "darling_core"
+version = "0.14.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a784d2ccaf7c98501746bf0be29b2022ba41fd62a2e622af997a03e9f972859f"
+dependencies = [
+ "fnv",
+ "ident_case",
+ "proc-macro2",
+ "quote",
+ "strsim",
+ "syn",
+]
+
+[[package]]
+name = "darling_macro"
+version = "0.14.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7618812407e9402654622dd402b0a89dff9ba93badd6540781526117b92aab7e"
+dependencies = [
+ "darling_core",
+ "quote",
+ "syn",
+]
+
+[[package]]
+name = "defer-drop"
+version = "1.3.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f613ec9fa66a6b28cdb1842b27f9adf24f39f9afc4dcdd9fdecee4aca7945c57"
+dependencies = [
+ "crossbeam-channel",
+ "once_cell",
+]
+
+[[package]]
+name = "derive_builder"
+version = "0.11.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d07adf7be193b71cc36b193d0f5fe60b918a3a9db4dad0449f57bcfd519704a3"
+dependencies = [
+ "derive_builder_macro",
+]
+
+[[package]]
+name = "derive_builder_core"
+version = "0.11.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1f91d4cfa921f1c05904dc3c57b4a32c38aed3340cce209f3a6fd1478babafc4"
+dependencies = [
+ "darling",
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
+name = "derive_builder_macro"
+version = "0.11.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8f0314b72bed045f3a68671b3c86328386762c93f82d98c65c3cb5e5f573dd68"
+dependencies = [
+ "derive_builder_core",
+ "syn",
+]
+
+[[package]]
 name = "digest"
 version = "0.10.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -548,6 +669,16 @@ dependencies = [
 ]
 
 [[package]]
+name = "dirs-next"
+version = "2.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b98cf8ebf19c3d1b223e151f99a4f9f0690dca41414773390fc824184ac833e1"
+dependencies = [
+ "cfg-if",
+ "dirs-sys-next",
+]
+
+[[package]]
 name = "dirs-sys"
 version = "0.3.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -559,6 +690,17 @@ dependencies = [
 ]
 
 [[package]]
+name = "dirs-sys-next"
+version = "0.1.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "4ebda144c4fe02d1f7ea1a7d9641b6fc6b580adcfa024ae48797ecdeb6825b4d"
+dependencies = [
+ "libc",
+ "redox_users",
+ "winapi",
+]
+
+[[package]]
 name = "dotenvy"
 version = "0.15.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -768,6 +910,15 @@ dependencies = [
 ]
 
 [[package]]
+name = "fuzzy-matcher"
+version = "0.3.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "54614a3312934d066701a80f20f15fa3b56d67ac7722b39eea5b4c9dd1d66c94"
+dependencies = [
+ "thread_local",
+]
+
+[[package]]
 name = "generic-array"
 version = "0.14.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -974,6 +1125,12 @@ dependencies = [
 ]
 
 [[package]]
+name = "ident_case"
+version = "1.0.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b9e0384b61958566e926dc50660321d12159025e767c18e043daf26b70104c39"
+
+[[package]]
 name = "idna"
 version = "0.3.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1195,6 +1352,24 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "2dffe52ecf27772e601905b7522cb4ef790d2cc203488bbd0e2fe85fcb74566d"
 
 [[package]]
+name = "memoffset"
+version = "0.6.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5aa361d4faea93603064a027415f07bd8e1d5c88c9fbf68bf56a285428fd79ce"
+dependencies = [
+ "autocfg",
+]
+
+[[package]]
+name = "memoffset"
+version = "0.7.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5de893c32cde5f383baa4c04c5d6dbdd735cfd4a794b0debdb2bb1b421da5ff4"
+dependencies = [
+ "autocfg",
+]
+
+[[package]]
 name = "mime"
 version = "0.3.16"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1225,6 +1400,31 @@ dependencies = [
 ]
 
 [[package]]
+name = "nix"
+version = "0.24.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "fa52e972a9a719cecb6864fb88568781eb706bac2cd1d4f04a648542dbf78069"
+dependencies = [
+ "bitflags",
+ "cfg-if",
+ "libc",
+]
+
+[[package]]
+name = "nix"
+version = "0.25.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f346ff70e7dbfd675fe90590b92d59ef2de15a8779ae305ebcbfd3f0caf59be4"
+dependencies = [
+ "autocfg",
+ "bitflags",
+ "cfg-if",
+ "libc",
+ "memoffset 0.6.5",
+ "pin-utils",
+]
+
+[[package]]
 name = "nom"
 version = "7.1.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1564,6 +1764,28 @@ dependencies = [
 ]
 
 [[package]]
+name = "rayon"
+version = "1.6.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6db3a213adf02b3bcfd2d3846bb41cb22857d131789e01df434fb7e7bc0759b7"
+dependencies = [
+ "either",
+ "rayon-core",
+]
+
+[[package]]
+name = "rayon-core"
+version = "1.10.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "356a0625f1954f730c0201cdab48611198dc6ce21f4acff55089b5a78e6e835b"
+dependencies = [
+ "crossbeam-channel",
+ "crossbeam-deque",
+ "crossbeam-utils",
+ "num_cpus",
+]
+
+[[package]]
 name = "redox_syscall"
 version = "0.2.16"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1972,6 +2194,31 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "e90531723b08e4d6d71b791108faf51f03e1b4a7784f96b2b87f852ebc247228"
 
 [[package]]
+name = "skim"
+version = "0.10.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "cebed5f897cd6c0d80fbe30adb36c0abf7400e93043a63ae56458495642b3485"
+dependencies = [
+ "beef",
+ "bitflags",
+ "chrono",
+ "crossbeam",
+ "defer-drop",
+ "derive_builder",
+ "fuzzy-matcher",
+ "lazy_static",
+ "log",
+ "nix 0.25.1",
+ "rayon",
+ "regex",
+ "time 0.3.17",
+ "timer",
+ "tuikit",
+ "unicode-width",
+ "vte",
+]
+
+[[package]]
 name = "slab"
 version = "0.4.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2193,6 +2440,17 @@ dependencies = [
 ]
 
 [[package]]
+name = "term"
+version = "0.7.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c59df8ac95d96ff9bede18eb7300b0fda5e5d8d90960e76f8e14ae765eedbf1f"
+dependencies = [
+ "dirs-next",
+ "rustversion",
+ "winapi",
+]
+
+[[package]]
 name = "termcolor"
 version = "1.1.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2252,6 +2510,31 @@ dependencies = [
 ]
 
 [[package]]
+name = "time"
+version = "0.3.17"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a561bf4617eebd33bca6434b988f39ed798e527f51a1e797d0ee4f61c0a38376"
+dependencies = [
+ "serde",
+ "time-core",
+]
+
+[[package]]
+name = "time-core"
+version = "0.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2e153e1f1acaef8acc537e68b44906d2db6436e2b35ac2c6b42640fff91f00fd"
+
+[[package]]
+name = "timer"
+version = "0.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "31d42176308937165701f50638db1c31586f183f1aab416268216577aec7306b"
+dependencies = [
+ "chrono",
+]
+
+[[package]]
 name = "tiny-bip39"
 version = "1.0.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2465,6 +2748,20 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "59547bce71d9c38b83d9c0e92b6066c4253371f15005def0c30d9657f50c7642"
 
 [[package]]
+name = "tuikit"
+version = "0.5.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5e19c6ab038babee3d50c8c12ff8b910bdb2196f62278776422f50390d8e53d8"
+dependencies = [
+ "bitflags",
+ "lazy_static",
+ "log",
+ "nix 0.24.3",
+ "term",
+ "unicode-width",
+]
+
+[[package]]
 name = "typenum"
 version = "1.15.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2539,6 +2836,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "e8db7427f936968176eaa7cdf81b7f98b980b18495ec28f1b5791ac3bfe3eea9"
 
 [[package]]
+name = "utf8parse"
+version = "0.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "936e4b492acfd135421d8dca4b1aa80a7bfc26e702ef3af710e0752684df5372"
+
+[[package]]
 name = "uuid"
 version = "1.2.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2560,6 +2863,27 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "49874b5167b65d7193b8aba1567f5c7d93d001cafc34600cee003eda787e483f"
 
 [[package]]
+name = "vte"
+version = "0.11.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1aae21c12ad2ec2d168c236f369c38ff332bc1134f7246350dca641437365045"
+dependencies = [
+ "arrayvec",
+ "utf8parse",
+ "vte_generate_state_changes",
+]
+
+[[package]]
+name = "vte_generate_state_changes"
+version = "0.1.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d257817081c7dffcdbab24b9e62d2def62e2ff7d00b1c20062551e6cccc145ff"
+dependencies = [
+ "proc-macro2",
+ "quote",
+]
+
+[[package]]
 name = "walkdir"
 version = "2.3.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/Cargo.toml b/Cargo.toml
index 5b47505e8..f26348518 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -73,6 +73,7 @@ semver = "1.0.14"
 runtime-format = "0.1.2"
 tiny-bip39 = "1"
 futures-util = "0.3"
+skim = { version = "0.10.2", default-features = false }
 
 # from tui
 bitflags = "1.3"
diff --git a/atuin-client/src/database.rs b/atuin-client/src/database.rs
index 3b5791539..b24020c0c 100644
--- a/atuin-client/src/database.rs
+++ b/atuin-client/src/database.rs
@@ -21,9 +21,9 @@ use super::{
 };
 
 pub struct Context {
-    session: String,
-    cwd: String,
-    hostname: String,
+    pub session: String,
+    pub cwd: String,
+    pub hostname: String,
 }
 
 pub fn current_context() -> Context {
@@ -85,6 +85,8 @@ pub trait Database: Send + Sync {
     ) -> Result<Vec<History>>;
 
     async fn query_history(&self, query: &str) -> Result<Vec<History>>;
+
+    async fn all_with_count(&self) -> Result<Vec<(History, i32)>>;
 }
 
 // Intended for use on a developer machine and not a sync server.
@@ -428,7 +430,7 @@ impl Database for Sqlite {
         match search_mode {
             SearchMode::Prefix => sql.and_where_like_left("command", query),
             SearchMode::FullText => sql.and_where_like_any("command", query),
-            SearchMode::Fuzzy => {
+            SearchMode::Skim | SearchMode::Fuzzy => {
                 // don't recompile the regex on successive calls!
                 lazy_static! {
                     static ref SPLIT_REGEX: Regex = Regex::new(r" +").unwrap();
@@ -492,6 +494,40 @@ impl Database for Sqlite {
 
         Ok(res)
     }
+
+    async fn all_with_count(&self) -> Result<Vec<(History, i32)>> {
+        debug!("listing history");
+
+        let mut query = SqlBuilder::select_from(SqlName::new("history").alias("h").baquoted());
+
+        query
+            .fields(&[
+                "id",
+                "max(timestamp) as timestamp",
+                "max(duration) as duration",
+                "exit",
+                "command",
+                "group_concat(cwd, ':') as cwd",
+                "group_concat(session) as session",
+                "group_concat(hostname, ',') as hostname",
+                "count(*) as count",
+            ])
+            .group_by("command")
+            .group_by("exit")
+            .order_desc("timestamp");
+
+        let query = query.sql().expect("bug in list query. please report");
+
+        let res = sqlx::query(&query)
+            .map(|row: SqliteRow| {
+                let count: i32 = row.get("count");
+                (Self::query_history(row), count)
+            })
+            .fetch_all(&self.pool)
+            .await?;
+
+        Ok(res)
+    }
 }
 
 #[cfg(test)]
diff --git a/atuin-client/src/settings.rs b/atuin-client/src/settings.rs
index aab2f4a33..de9bd640b 100644
--- a/atuin-client/src/settings.rs
+++ b/atuin-client/src/settings.rs
@@ -18,7 +18,7 @@ pub const LAST_SYNC_FILENAME: &str = "last_sync_time";
 pub const LAST_VERSION_CHECK_FILENAME: &str = "last_version_check_time";
 pub const LATEST_VERSION_FILENAME: &str = "latest_version";
 
-#[derive(Clone, Debug, Deserialize, Copy, ValueEnum)]
+#[derive(Clone, Debug, Deserialize, Copy, ValueEnum, PartialEq)]
 pub enum SearchMode {
     #[serde(rename = "prefix")]
     Prefix,
@@ -29,6 +29,9 @@ pub enum SearchMode {
 
     #[serde(rename = "fuzzy")]
     Fuzzy,
+
+    #[serde(rename = "skim")]
+    Skim,
 }
 
 #[derive(Clone, Debug, Deserialize, Copy, PartialEq, Eq, ValueEnum)]
diff --git a/src/command/client/search.rs b/src/command/client/search.rs
index 8d0e1de46..0a728cc50 100644
--- a/src/command/client/search.rs
+++ b/src/command/client/search.rs
@@ -16,6 +16,7 @@ mod cursor;
 mod duration;
 mod history_list;
 mod interactive;
+mod skim_impl;
 pub use duration::{format_duration, format_duration_into};
 
 #[allow(clippy::struct_excessive_bools)]
diff --git a/src/command/client/search/history_list.rs b/src/command/client/search/history_list.rs
index 9e266fe9c..27a8b2944 100644
--- a/src/command/client/search/history_list.rs
+++ b/src/command/client/search/history_list.rs
@@ -1,4 +1,4 @@
-use std::time::Duration;
+use std::{sync::Arc, time::Duration};
 
 use crate::tui::{
     buffer::Buffer,
@@ -8,10 +8,10 @@ use crate::tui::{
 };
 use atuin_client::history::History;
 
-use super::format_duration;
+use super::{format_duration, interactive::HistoryWrapper};
 
 pub struct HistoryList<'a> {
-    history: &'a [History],
+    history: &'a [Arc<HistoryWrapper>],
     block: Option<Block<'a>>,
 }
 
@@ -77,7 +77,7 @@ impl<'a> StatefulWidget for HistoryList<'a> {
 }
 
 impl<'a> HistoryList<'a> {
-    pub fn new(history: &'a [History]) -> Self {
+    pub fn new(history: &'a [Arc<HistoryWrapper>]) -> Self {
         Self {
             history,
             block: None,
diff --git a/src/command/client/search/interactive.rs b/src/command/client/search/interactive.rs
index 45c532f06..c1d1c175b 100644
--- a/src/command/client/search/interactive.rs
+++ b/src/command/client/search/interactive.rs
@@ -1,16 +1,10 @@
 use std::{
     io::{stdout, Write},
+    ops::Deref,
+    sync::Arc,
     time::Duration,
 };
 
-use crate::tui::{
-    backend::{Backend, CrosstermBackend},
-    layout::{Alignment, Constraint, Direction, Layout},
-    style::{Color, Modifier, Style},
-    text::{Span, Spans, Text},
-    widgets::{Block, BorderType, Borders, Paragraph},
-    Frame, Terminal,
-};
 use crossterm::{
     event::{self, Event, KeyCode, KeyEvent, KeyModifiers, MouseEvent},
     execute, terminal,
@@ -18,12 +12,12 @@ 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::Context,
     database::Database,
+    database::{current_context, Context},
     history::History,
     settings::{ExitMode, FilterMode, SearchMode, Settings},
 };
@@ -32,18 +26,35 @@ use super::{
     cursor::Cursor,
     history_list::{HistoryList, ListState, PREFIX_LENGTH},
 };
-use crate::VERSION;
+use crate::{
+    tui::{
+        backend::{Backend, CrosstermBackend},
+        layout::{Alignment, Constraint, Direction, Layout},
+        style::{Color, Modifier, Style},
+        text::{Span, Spans, Text},
+        widgets::{Block, BorderType, Borders, Paragraph},
+        Frame, Terminal,
+    },
+    VERSION,
+};
 
 const RETURN_ORIGINAL: usize = usize::MAX;
 const RETURN_QUERY: usize = usize::MAX - 1;
 
 struct State {
     history_count: i64,
-    input: Cursor,
-    filter_mode: FilterMode,
-    results_state: ListState,
-    context: Context,
     update_needed: Option<Version>,
+    results_state: ListState,
+    search: SearchState,
+
+    // only allocated if using skim
+    all_history: Vec<Arc<HistoryWrapper>>,
+}
+
+pub struct SearchState {
+    pub input: Cursor,
+    pub filter_mode: FilterMode,
+    pub context: Context,
 }
 
 impl State {
@@ -51,22 +62,48 @@ impl State {
         &mut self,
         search_mode: SearchMode,
         db: &mut impl Database,
-    ) -> Result<Vec<History>> {
-        let i = self.input.as_str();
+    ) -> Result<Vec<Arc<HistoryWrapper>>> {
+        let i = self.search.input.as_str();
         let results = if i.is_empty() {
-            db.list(self.filter_mode, &self.context, Some(200), true)
-                .await?
+            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::<Vec<_>>()
+        } else if 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::<Vec<_>>();
+            }
+
+            super::skim_impl::fuzzy_search(&self.search, &self.all_history).await
         } else {
             db.search(
                 search_mode,
-                self.filter_mode,
-                &self.context,
+                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::<Vec<_>>()
         };
 
         self.results_state.select(0);
@@ -125,47 +162,51 @@ impl State {
                 return Some(self.results_state.selected() + c);
             }
             KeyCode::Left if ctrl => self
+                .search
                 .input
                 .prev_word(&settings.word_chars, settings.word_jump_mode),
             KeyCode::Left => {
-                self.input.left();
+                self.search.input.left();
             }
             KeyCode::Char('h') if ctrl => {
-                self.input.left();
+                self.search.input.left();
             }
             KeyCode::Right if ctrl => self
+                .search
                 .input
                 .next_word(&settings.word_chars, settings.word_jump_mode),
-            KeyCode::Right => self.input.right(),
-            KeyCode::Char('l') if ctrl => self.input.right(),
-            KeyCode::Char('a') if ctrl => self.input.start(),
-            KeyCode::Home => self.input.start(),
-            KeyCode::Char('e') if ctrl => self.input.end(),
-            KeyCode::End => self.input.end(),
+            KeyCode::Right => self.search.input.right(),
+            KeyCode::Char('l') if ctrl => self.search.input.right(),
+            KeyCode::Char('a') if ctrl => self.search.input.start(),
+            KeyCode::Home => self.search.input.start(),
+            KeyCode::Char('e') if ctrl => self.search.input.end(),
+            KeyCode::End => self.search.input.end(),
             KeyCode::Backspace if ctrl => self
+                .search
                 .input
                 .remove_prev_word(&settings.word_chars, settings.word_jump_mode),
             KeyCode::Backspace => {
-                self.input.back();
+                self.search.input.back();
             }
             KeyCode::Delete if ctrl => self
+                .search
                 .input
                 .remove_next_word(&settings.word_chars, settings.word_jump_mode),
             KeyCode::Delete => {
-                self.input.remove();
+                self.search.input.remove();
             }
             KeyCode::Char('w') if ctrl => {
                 // remove the first batch of whitespace
-                while matches!(self.input.back(), Some(c) if c.is_whitespace()) {}
-                while self.input.left() {
-                    if self.input.char().unwrap().is_whitespace() {
-                        self.input.right(); // found whitespace, go back right
+                while matches!(self.search.input.back(), Some(c) if c.is_whitespace()) {}
+                while self.search.input.left() {
+                    if self.search.input.char().unwrap().is_whitespace() {
+                        self.search.input.right(); // found whitespace, go back right
                         break;
                     }
-                    self.input.remove();
+                    self.search.input.remove();
                 }
             }
-            KeyCode::Char('u') if ctrl => self.input.clear(),
+            KeyCode::Char('u') if ctrl => self.search.input.clear(),
             KeyCode::Char('r') if ctrl => {
                 pub static FILTER_MODES: [FilterMode; 4] = [
                     FilterMode::Global,
@@ -173,9 +214,9 @@ impl State {
                     FilterMode::Session,
                     FilterMode::Directory,
                 ];
-                let i = self.filter_mode as usize;
+                let i = self.search.filter_mode as usize;
                 let i = (i + 1) % FILTER_MODES.len();
-                self.filter_mode = FILTER_MODES[i];
+                self.search.filter_mode = FILTER_MODES[i];
             }
             KeyCode::Down if self.results_state.selected() == 0 => return Some(RETURN_ORIGINAL),
             KeyCode::Down => {
@@ -194,7 +235,7 @@ impl State {
                 let i = self.results_state.selected() + 1;
                 self.results_state.select(i.min(len - 1));
             }
-            KeyCode::Char(c) => self.input.insert(c),
+            KeyCode::Char(c) => self.search.input.insert(c),
             KeyCode::PageDown => {
                 let scroll_len = self.results_state.max_entries() - settings.scroll_context_lines;
                 let i = self.results_state.selected().saturating_sub(scroll_len);
@@ -216,7 +257,7 @@ impl State {
     fn draw<T: Backend>(
         &mut self,
         f: &mut Frame<'_, T>,
-        results: &[History],
+        results: &[Arc<HistoryWrapper>],
         compact: bool,
         show_preview: bool,
     ) {
@@ -284,7 +325,7 @@ impl State {
         let preview = self.build_preview(results, compact, preview_width, chunks[3].width.into());
         f.render_widget(preview, chunks[3]);
 
-        let extra_width = UnicodeWidthStr::width(self.input.substring());
+        let extra_width = UnicodeWidthStr::width(self.search.input.substring());
 
         let cursor_offset = if compact { 0 } else { 1 };
         f.set_cursor(
@@ -332,7 +373,7 @@ impl State {
         stats
     }
 
-    fn build_results_list(compact: bool, results: &[History]) -> HistoryList {
+    fn build_results_list(compact: bool, results: &[Arc<HistoryWrapper>]) -> HistoryList {
         let results_list = if compact {
             HistoryList::new(results)
         } else {
@@ -348,8 +389,8 @@ impl State {
     fn build_input(&mut self, compact: bool, chunk_width: usize) -> Paragraph {
         let input = format!(
             "[{:^14}] {}",
-            self.filter_mode.as_str(),
-            self.input.as_str(),
+            self.search.filter_mode.as_str(),
+            self.search.input.as_str(),
         );
         let input = if compact {
             Paragraph::new(input)
@@ -366,7 +407,7 @@ impl State {
 
     fn build_preview(
         &mut self,
-        results: &[History],
+        results: &[Arc<HistoryWrapper>],
         compact: bool,
         preview_width: u16,
         chunk_width: usize,
@@ -438,6 +479,23 @@ 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<str> {
+        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
@@ -455,22 +513,28 @@ pub async fn history(
     // Put the cursor at the end of the query by default
     input.end();
 
-    let update_needed = settings.needs_update().fuse();
+    let settings2 = settings.clone();
+    let update_needed = tokio::spawn(async move { settings2.needs_update().await }).fuse();
     tokio::pin!(update_needed);
 
+    let context = current_context();
+
     let mut app = State {
         history_count: db.history_count().await?,
-        input,
         results_state: ListState::default(),
-        context: current_context(),
-        filter_mode: if settings.shell_up_key_binding {
-            settings
-                .filter_mode_shell_up_key_binding
-                .unwrap_or(settings.filter_mode)
-        } else {
-            settings.filter_mode
-        },
         update_needed: None,
+        search: SearchState {
+            input,
+            context,
+            filter_mode: if settings.shell_up_key_binding {
+                settings
+                    .filter_mode_shell_up_key_binding
+                    .unwrap_or(settings.filter_mode)
+            } else {
+                settings.filter_mode
+            },
+        },
+        all_history: Vec::new(),