1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
use std::path::Path;
use async_trait::async_trait;
use atuin_client::{
database::Database, history::History, result::HistoryResult, 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<HistoryResult>,
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<Vec<HistoryResult>> {
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: &[HistoryResult],
) -> Vec<HistoryResult> {
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, res) in all_history.iter().enumerate() {
let history = &res.history;
let count = &res.count;
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, res.clone());
let mut j = i + 1;
while j < set.len() {
// remove duplicates that have a worse score
if set[j].history.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].history.command == history.command {
break 'insert;
}
}
if set.len() < 200 {
ranks.push(score);
set.push(res.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
}
|
