norm/metrics/fzf/
slab.rs

1use core::ops::{Index, IndexMut};
2
3use super::Score;
4
5/// Creating a new [`V2Slab`] allocates 5.25kb on a 64-bit system and 4.25kb on
6/// a 32-bit system.
7#[derive(Clone, Default)]
8pub(super) struct V2Slab {
9    /// TODO: docs
10    pub(super) bonus: BonusSlab,
11
12    /// TODO: docs
13    pub(super) consecutive_matrix: MatrixSlab<usize>,
14
15    /// TODO: docs
16    pub(super) matched_indices: MatchedIndicesSlab,
17
18    /// TODO: docs
19    pub(super) scoring_matrix: MatrixSlab<Score>,
20}
21
22/// TODO: docs
23#[derive(Clone, Default)]
24pub(super) struct Bonus {
25    value: u8,
26    is_set: bool,
27}
28
29impl Bonus {
30    #[inline(always)]
31    pub fn is_set(&self) -> bool {
32        self.is_set
33    }
34
35    #[inline(always)]
36    pub fn set(&mut self, value: Score) {
37        self.value = value as _;
38        self.is_set = true;
39    }
40
41    #[inline(always)]
42    pub fn value(&self) -> Score {
43        self.value as _
44    }
45}
46
47/// Creating a new [`BonusSlab`] allocates 256 bytes.
48#[derive(Clone)]
49pub(super) struct BonusSlab {
50    vec: Vec<Bonus>,
51}
52
53impl Default for BonusSlab {
54    #[inline(always)]
55    fn default() -> Self {
56        Self { vec: vec![Bonus::default(); 128] }
57    }
58}
59
60impl BonusSlab {
61    /// TODO: docs
62    #[inline]
63    pub fn alloc(&mut self, len: usize) -> &mut [Bonus] {
64        if len > self.vec.len() {
65            self.vec.resize(len, Bonus::default());
66        }
67
68        let slice = &mut self.vec[..len];
69
70        for bonus in slice.iter_mut() {
71            bonus.is_set = false;
72        }
73
74        slice
75    }
76}
77
78/// Creating a new [`CandidateSlab`] allocates 512 bytes.
79#[derive(Clone)]
80pub(super) struct CandidateSlab {
81    chars: Vec<char>,
82}
83
84impl Default for CandidateSlab {
85    #[inline(always)]
86    fn default() -> Self {
87        Self { chars: vec![char::default(); 128] }
88    }
89}
90
91impl CandidateSlab {
92    #[inline(always)]
93    pub fn alloc<'a>(&'a mut self, text: &str) -> &'a [char] {
94        if text.len() > self.chars.len() {
95            self.chars.resize(text.len(), char::default());
96        }
97
98        let mut char_len = 0;
99
100        for ch in text.chars() {
101            self.chars[char_len] = ch;
102            char_len += 1;
103        }
104
105        &self.chars[..char_len]
106    }
107}
108
109/// Creating a new [`MatchedIndicesSlab`] allocates 1kb on a 64-bit system.
110#[derive(Clone)]
111pub(super) struct MatchedIndicesSlab {
112    vec: Vec<usize>,
113}
114
115impl Default for MatchedIndicesSlab {
116    #[inline]
117    fn default() -> Self {
118        Self { vec: vec![0; 128] }
119    }
120}
121
122impl MatchedIndicesSlab {
123    #[inline]
124    /// TODO: docs
125    pub fn alloc(&mut self, len: usize) -> &mut [usize] {
126        if len > self.vec.len() {
127            self.vec.resize(len, 0);
128        }
129
130        &mut self.vec[..len]
131    }
132}
133
134pub(super) trait MatrixItem: Copy + Ord + core::fmt::Display {
135    /// TODO: docs
136    fn fill() -> Self;
137
138    /// TODO: docs
139    fn printed_width(&self) -> usize;
140}
141
142impl MatrixItem for Score {
143    #[inline]
144    fn fill() -> Self {
145        0
146    }
147
148    fn printed_width(&self) -> usize {
149        if *self == 0 {
150            1
151        } else {
152            (self.ilog10() + 1) as usize
153        }
154    }
155}
156
157impl MatrixItem for usize {
158    #[inline]
159    fn fill() -> Self {
160        0
161    }
162
163    fn printed_width(&self) -> usize {
164        if *self == 0 {
165            1
166        } else {
167            (self.ilog10() + 1) as usize
168        }
169    }
170}
171
172/// Creating a new [`MatrixSlab`] allocates `256 * size_of::<T>()` bytes.
173#[derive(Clone)]
174pub(super) struct MatrixSlab<T: MatrixItem> {
175    vec: Vec<T>,
176}
177
178impl<T: Default + MatrixItem> Default for MatrixSlab<T> {
179    #[inline]
180    fn default() -> MatrixSlab<T> {
181        // We allocate a 256 cell matrix slab by default to minimize the
182        // need to re-allocate for long `query * candidate` pairs.
183        Self { vec: vec![T::default(); 256] }
184    }
185}
186
187impl<T: MatrixItem> MatrixSlab<T> {
188    /// TODO: docs
189    #[inline]
190    pub fn alloc(&mut self, width: usize, height: usize) -> Matrix<'_, T> {
191        debug_assert!(height * width > 0);
192
193        if height * width > self.vec.len() {
194            self.vec.resize(height * width, T::fill());
195        }
196
197        let slice = &mut self.vec[..height * width];
198
199        slice.fill(T::fill());
200
201        Matrix { slice, height, width }
202    }
203}
204
205/// TODO: docs
206pub(super) struct Matrix<'a, T: MatrixItem> {
207    /// TODO: docs
208    ///
209    /// <width><width>...<width>
210    /// \---- height times ----/
211    slice: &'a mut [T],
212    height: usize,
213    width: usize,
214}
215
216/// Prints the matrix like this:
217///
218/// ```text
219///   ┌                         ┐
220///   │0  16 16 13 12 11 10 9  8│
221///   │0  0  0  0  0  0  0  0  0│
222///   │0  0  0  0  0  0  0  0  0│
223///   └                         ┘
224/// ```
225impl<T: MatrixItem> core::fmt::Debug for Matrix<'_, T> {
226    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
227        use core::fmt::Write;
228
229        // The matrix should never be empty, but just in case.
230        if self.slice.is_empty() {
231            return f.write_str("[ ]");
232        }
233
234        // The character width of the biggest score in the whole matrix.
235        let max_score_width = {
236            let max_score = self.slice.iter().copied().max().unwrap();
237            max_score.printed_width()
238        };
239
240        // The character width of the biggest score in the last column.
241        let last_col_max_score_width = {
242            // The cell in the last column of the first row.
243            let first_row_last_col =
244                self.cols(self.top_left()).last().unwrap();
245
246            let last_col_max_score = self
247                .rows(first_row_last_col)
248                .map(|cell| self[cell])
249                .max()
250                .unwrap();
251
252            last_col_max_score.printed_width()
253        };
254
255        let printed_matrix_inner_width = (self.width - 1)
256            * (max_score_width + 1)
257            + last_col_max_score_width;
258
259        let opening_char: char;
260
261        let closing_char: char;
262
263        if self.height == 1 {
264            opening_char = '[';
265            closing_char = ']';
266        } else {
267            f.write_char('┌')?;
268            f.write_str(&" ".repeat(printed_matrix_inner_width))?;
269            f.write_char('┐')?;
270            f.write_char('\n')?;
271            opening_char = '│';
272            closing_char = '│';
273        }
274
275        for cell in self.rows(self.top_left()) {
276            f.write_char(opening_char)?;
277
278            for cell in self.cols(cell) {
279                let item = self[cell];
280
281                write!(f, "{item}")?;
282
283                let num_spaces = if self.col_of(cell) + 1 == self.width {
284                    last_col_max_score_width - item.printed_width()
285                } else {
286                    max_score_width - item.printed_width() + 1
287                };
288
289                f.write_str(&" ".repeat(num_spaces))?;
290            }
291
292            f.write_char(closing_char)?;
293
294            f.write_char('\n')?;
295        }
296
297        if self.height > 1 {
298            f.write_char('└')?;
299            f.write_str(&" ".repeat(printed_matrix_inner_width))?;
300            f.write_char('┘')?;
301        }
302
303        Ok(())
304    }
305}
306
307impl<'a, T: MatrixItem + Copy> Matrix<'a, T> {
308    /// TODO: docs
309    #[inline(always)]
310    pub fn get_value(&self, cell: MatrixCell) -> Option<T> {
311        self.slice.get(cell.0).copied()
312    }
313}
314
315impl<'a, T: MatrixItem> Matrix<'a, T> {
316    /// TODO: docs
317    #[inline]
318    pub fn col_of(&self, cell: MatrixCell) -> usize {
319        cell.0 % self.width
320    }
321
322    /// TODO: docs
323    #[inline]
324    pub fn cols(&self, starting_from: MatrixCell) -> Cols {
325        Cols {
326            next: starting_from,
327            remaining: self.width - self.col_of(starting_from),
328        }
329    }
330
331    /// TODO: docs
332    #[inline]
333    pub fn down_right(&self, cell: MatrixCell) -> MatrixCell {
334        MatrixCell(cell.0 + self.width + 1)
335    }
336
337    /// TODO: docs
338    #[inline(always)]
339    pub fn height(&self) -> usize {
340        self.height
341    }
342
343    /// TODO: docs
344    #[inline]
345    pub fn left(&self, cell: MatrixCell) -> MatrixCell {
346        MatrixCell(cell.0 - 1)
347    }
348
349    /// TODO: docs
350    #[inline]
351    pub fn row_of(&self, cell: MatrixCell) -> usize {
352        cell.0 / self.width
353    }
354
355    /// TODO: docs
356    #[inline]
357    pub fn row_mut(&mut self, row: usize) -> &mut [T] {
358        let start = row * self.width;
359        let end = start + self.width;
360        &mut self.slice[start..end]
361    }
362
363    #[inline]
364    pub fn rows(&self, starting_from: MatrixCell) -> Rows {
365        Rows {
366            next: starting_from,
367            matrix_width: self.width,
368            remaining: self.height - self.row_of(starting_from),
369        }
370    }
371
372    /// TODO: docs
373    #[inline]
374    pub fn top_left(&self) -> MatrixCell {
375        MatrixCell(0)
376    }
377
378    /// TODO: docs
379    #[inline]
380    pub fn two_rows_mut(
381        &mut self,
382        row_idx_a: usize,
383        row_idx_b: usize,
384    ) -> (&mut Row<T>, &mut Row<T>) {
385        debug_assert!(row_idx_a < row_idx_b);
386
387        let start_b = row_idx_b * self.width;
388
389        let (part_a, part_b) = self.slice.split_at_mut(start_b);
390
391        let start_a = row_idx_a * self.width;
392
393        (&mut part_a[start_a..start_a + self.width], &mut part_b[..self.width])
394    }
395
396    #[inline]
397    pub fn up_left(&self, cell: MatrixCell) -> MatrixCell {
398        MatrixCell(cell.0 - self.width - 1)
399    }
400
401    /// TODO: docs
402    #[inline(always)]
403    pub fn width(&self) -> usize {
404        self.width
405    }
406}
407
408pub(super) type Row<T> = [T];
409
410#[derive(Debug, Clone, Copy)]
411pub(super) struct MatrixCell(pub(super) usize);
412
413impl<T: MatrixItem> Index<MatrixCell> for Matrix<'_, T> {
414    type Output = T;
415
416    #[inline]
417    fn index(&self, index: MatrixCell) -> &Self::Output {
418        &self.slice[index.0]
419    }
420}
421
422impl<T: MatrixItem> IndexMut<MatrixCell> for Matrix<'_, T> {
423    #[inline]
424    fn index_mut(&mut self, index: MatrixCell) -> &mut Self::Output {
425        &mut self.slice[index.0]
426    }
427}
428
429/// TODO: docs
430pub(super) struct Cols {
431    next: MatrixCell,
432    remaining: usize,
433}
434
435impl Iterator for Cols {
436    type Item = MatrixCell;
437
438    #[inline]
439    fn next(&mut self) -> Option<Self::Item> {
440        if self.remaining == 0 {
441            return None;
442        }
443        let this = self.next;
444        self.next.0 += 1;
445        self.remaining -= 1;
446        Some(this)
447    }
448}
449
450/// TODO: docs
451pub(super) struct Rows {
452    next: MatrixCell,
453    matrix_width: usize,
454    remaining: usize,
455}
456
457impl Iterator for Rows {
458    type Item = MatrixCell;
459
460    #[inline]
461    fn next(&mut self) -> Option<Self::Item> {
462        if self.remaining == 0 {
463            return None;
464        }
465        let this = self.next;
466        self.next.0 += self.matrix_width;
467        self.remaining -= 1;
468        Some(this)
469    }
470}
norm/metrics/fzf/slab.rs

norm/metrics/fzf/
slab.rs
