keyhammer/
highlight.rs

1// SPDX-License-Identifier: AGPL-3.0-or-later
2// Copyright (C) 2026 Robson Trasel
3
4//! Match highlighting: which characters of a hit the user typed.
5//!
6//! After a search, [`Searcher::highlight`] (or
7//! [`Searcher::highlight_text`] for [`Searcher::search_text`] queries)
8//! re-runs the alignment of the query with one hit's term and walks it back.
9//! It returns the parts of the caller's original term string that the
10//! alignment matched, as sorted, disjoint, half-open ranges in code points,
11//! UTF-8 bytes and UTF-16 units. Only call it for the hits you show: the
12//! search itself does no highlighting work.
13//!
14//! A term character is highlighted when it is aligned with an equal query
15//! character or is one of a transposed pair; substituted characters and
16//! characters the user skipped are not. The full rules (normalisation,
17//! partially matched characters such as `ß`, tie-breaking, prefix mode) are
18//! in `docs/design/highlighting.md`.
19//!
20//! ```
21//! use keyhammer::cost::CostModel;
22//! use keyhammer::highlight::HighlightMode;
23//! use keyhammer::search::{SearchConfig, Searcher};
24//! use keyhammer::text::Normalizer;
25//! use keyhammer::trie::Trie;
26//!
27//! let items = [("Coração", 10), ("Corrida", 5)];
28//! let trie = Trie::build_normalized(&items, &Normalizer::new()).unwrap();
29//! let cm = CostModel::qwerty();
30//! let mut s = Searcher::new();
31//! let q = "coracap"; // "p" for "o", a neighbouring key
32//! let out = s.search_text(&trie, &cm, q, &SearchConfig::default()).unwrap();
33//! let hit = &out.hits[0];
34//! // The string the caller inserted for this term.
35//! let source = items[trie.input_index(hit.id) as usize].0;
36//! let h = s.highlight_text(&trie, &cm, q, hit, source, HighlightMode::Whole).unwrap();
37//! assert_eq!(h.cost, hit.cost);
38//! // "Coraçã" is highlighted, the final "o" was mistyped.
39//! assert_eq!(h.ranges.len(), 1);
40//! assert_eq!(h.ranges[0].chars, 0..6);
41//! assert_eq!(h.ranges[0].utf8, 0..8); // ç and ã are two bytes each
42//! assert_eq!(h.ranges[0].utf16, 0..6);
43//! assert_eq!(&source[h.ranges[0].utf8.clone()], "Coraçã");
44//! ```
45//!
46//! [`Searcher::highlight`]: crate::search::Searcher::highlight
47//! [`Searcher::highlight_text`]: crate::search::Searcher::highlight_text
48//! [`Searcher::search_text`]: crate::search::Searcher::search_text
49
50use alloc::vec::Vec;
51use core::fmt;
52use core::ops::Range;
53
54use crate::cost::{Cost, CostModel, INF};
55use crate::search::{DELETE, Hit, INSERT, MAX_W, SUB, TRANSPOSE, moves};
56use crate::text::{Normalizer, SourceMap};
57use crate::trie::Trie;
58
59/// Which search produced the hit.
60#[non_exhaustive]
61#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
62pub enum HighlightMode {
63    /// A hit of [`Searcher::search`](crate::search::Searcher::search) or
64    /// [`Searcher::search_text`](crate::search::Searcher::search_text): the
65    /// whole term is aligned with the query.
66    #[default]
67    Whole,
68    /// A hit of [`Searcher::search_prefix`](crate::search::Searcher::search_prefix)
69    /// or [`Searcher::search_prefix_text`](crate::search::Searcher::search_prefix_text):
70    /// the query is aligned with the shortest prefix of the term that attains
71    /// the hit's cost, and the rest of the term is never highlighted.
72    Prefix,
73}
74
75/// One span of the caller's term string, in three units.
76///
77/// All three ranges are half-open and describe the same characters.
78#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
79pub struct MatchRange {
80    /// Code points (`str::chars` positions; Python `str` indices).
81    pub chars: Range<usize>,
82    /// UTF-8 bytes: always on `char` boundaries, so `&source[r.utf8]` works.
83    pub utf8: Range<usize>,
84    /// UTF-16 code units (JavaScript string indices); never splits a
85    /// surrogate pair.
86    pub utf16: Range<usize>,
87}
88
89/// The highlighting of one hit.
90#[non_exhaustive]
91#[derive(Clone, Debug, Default, PartialEq, Eq)]
92pub struct Highlight {
93    /// The highlighted spans of the source string: sorted, disjoint, never
94    /// empty and never touching (at least one character between two spans).
95    pub ranges: Vec<MatchRange>,
96    /// The span of the source string the query was aligned with: the whole
97    /// term in [`HighlightMode::Whole`], the matched prefix in
98    /// [`HighlightMode::Prefix`]. Every range lies within it.
99    pub aligned: MatchRange,
100    /// The cost of the alignment behind the ranges: always equal to the
101    /// hit's [`Hit::cost`].
102    pub cost: Cost,
103    /// Dynamic-programming cells computed (the deterministic work counter).
104    pub cells: usize,
105}
106
107/// Why a hit could not be highlighted.
108#[derive(Clone, Copy, Debug, PartialEq, Eq)]
109#[non_exhaustive]
110pub enum HighlightError {
111    /// The query is longer than [`MAX_QUERY_LEN`](crate::search::MAX_QUERY_LEN).
112    QueryTooLong {
113        /// Query length in code points (after normalisation for
114        /// `highlight_text`).
115        len: usize,
116        /// The limit.
117        max: usize,
118    },
119    /// The hit's id is not a term of this trie.
120    UnknownTerm {
121        /// The id.
122        id: u32,
123    },
124    /// The source string does not normalise (with the trie's normaliser, if
125    /// any) to the hit's term.
126    SourceMismatch,
127    /// The alignment of this query and term does not cost what the hit says:
128    /// the hit comes from another query, cost model, trie or mode.
129    CostMismatch {
130        /// The hit's cost.
131        expected: Cost,
132        /// The recomputed cost, or `None` when it was not computed because it
133        /// certainly exceeds `expected` (or `expected` exceeds any budget a
134        /// search accepts).
135        found: Option<Cost>,
136    },
137}
138
139impl fmt::Display for HighlightError {
140    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
141        match self {
142            HighlightError::QueryTooLong { len, max } => {
143                write!(f, "query has {len} code points, the limit is {max}")
144            }
145            HighlightError::UnknownTerm { id } => write!(f, "no term with id {id}"),
146            HighlightError::SourceMismatch => {
147                f.write_str("the source string does not normalise to the hit's term")
148            }
149            HighlightError::CostMismatch {
150                expected,
151                found: Some(found),
152            } => write!(
153                f,
154                "the alignment costs {found}, the hit says {expected}: not a hit of this query"
155            ),
156            HighlightError::CostMismatch {
157                expected,
158                found: None,
159            } => write!(
160                f,
161                "no alignment can cost {expected}: not a hit of this query"
162            ),
163        }
164    }
165}
166
167/// What the traceback decided for one normalised term symbol.
168#[derive(Clone, Copy, Debug, PartialEq, Eq)]
169pub(crate) enum Status {
170    /// After the aligned prefix (prefix mode).
171    Unaligned,
172    /// Aligned with an equal query symbol.
173    Matched,
174    /// Aligned with a different query symbol.
175    Substituted,
176    /// One of a transposed pair.
177    Transposed,
178    /// Skipped by the user (an insertion).
179    Skipped,
180}
181
182impl Status {
183    fn highlighted(self) -> bool {
184        matches!(self, Status::Matched | Status::Transposed)
185    }
186}
187
188/// Reusable buffers of the traceback, kept in the `Searcher`.
189#[derive(Default)]
190pub(crate) struct Scratch {
191    /// The DP matrix, row `j` (term prefix length) after row `j - 1`.
192    d: Vec<Cost>,
193    /// The term symbols.
194    t: Vec<u32>,
195    /// One status per term symbol.
196    pub(crate) status: Vec<Status>,
197    /// The walked path, end first: (move, i, j) of each cell left.
198    pub(crate) path: Vec<(usize, usize, usize)>,
199    map: SourceMap,
200}
201
202/// Computes the matrix, checks the cost and walks the path back; fills
203/// `s.status` and `s.path`. Returns the aligned prefix length and the cells
204/// computed.
205pub(crate) fn align(
206    s: &mut Scratch,
207    cm: &CostModel,
208    q: &[u32],
209    mode: HighlightMode,
210    expected: Cost,
211) -> Result<(usize, usize), HighlightError> {
212    let (m, n) = (q.len(), s.t.len());
213    let mismatch = HighlightError::CostMismatch {
214        expected,
215        found: None,
216    };
217    // A hit above the largest budget cannot come from a search, and a prefix
218    // longer than `m + reach` needs more than `expected` in insertions.
219    if expected > MAX_W as Cost * cm.c_indel_min() {
220        return Err(mismatch);
221    }
222    let reach = usize::from(expected / cm.c_indel_min());
223    let jmax = match mode {
224        HighlightMode::Prefix => n.min(m + reach),
225        HighlightMode::Whole if n > m + reach || m > n + reach => return Err(mismatch),
226        HighlightMode::Whole => n,
227    };
228    let w = m + 1;
229    let cells = (jmax + 1) * w;
230    s.d.clear();
231    s.d.resize(cells, INF);
232    let (d, t) = (&mut s.d, &s.t);
233    let cell = |d: &[Cost], j: usize, i: usize| d[j * w + i];
234    // The candidates of cell (i, j), from the same function as the search.
235    let cand = |d: &[Cost], j: usize, i: usize| {
236        let ch = if j >= 1 { t[j - 1] } else { 0 };
237        let parent = if j >= 2 { Some(t[j - 2]) } else { None };
238        let diag = if j >= 1 && i >= 1 {
239            cell(d, j - 1, i - 1)
240        } else {
241            INF
242        };
243        let up = if j >= 1 { cell(d, j - 1, i) } else { INF };
244        let left = if i >= 1 { cell(d, j, i - 1) } else { INF };
245        let skip2 = if j >= 2 && i >= 2 {
246            cell(d, j - 2, i - 2)
247        } else {
248            INF
249        };
250        moves(cm, q, i, ch, parent, diag, up, left, skip2)
251    };
252    d[0] = 0;
253    for j in 0..=jmax {
254        for i in 0..=m {
255            if i + j > 0 {
256                let c = cand(d, j, i);
257                d[j * w + i] = c[SUB].min(c[TRANSPOSE]).min(c[INSERT]).min(c[DELETE]);
258            }
259        }
260    }
261    // Whole: the full term. Prefix: the shortest prefix of minimal cost.
262    let end = match mode {
263        HighlightMode::Prefix => (0..=jmax).min_by_key(|&j| (cell(d, j, m), j)).unwrap_or(0),
264        HighlightMode::Whole => n,
265    };
266    let cost = cell(d, end, m);
267    if cost != expected {
268        return Err(HighlightError::CostMismatch {
269            expected,
270            found: (cost < INF).then_some(cost),
271        });
272    }
273    s.status.clear();
274    s.status.resize(n, Status::Unaligned);
275    s.path.clear();
276    let (mut j, mut i) = (end, m);
277    while i + j > 0 {
278        let v = cell(d, j, i);
279        let c = cand(d, j, i);
280        // Tie-breaking: the first move, in this order, that attains the cell.
281        let Some(mv) = [SUB, TRANSPOSE, INSERT, DELETE]
282            .into_iter()
283            .find(|&k| c[k] == v)
284        else {
285            // Unreachable: every finite cell is attained by one of its moves.
286            break;
287        };
288        s.path.push((mv, i, j));
289        match mv {
290            SUB => {
291                s.status[j - 1] = if q[i - 1] == t[j - 1] {
292                    Status::Matched
293                } else {
294                    Status::Substituted
295                };
296                (i, j) = (i - 1, j - 1);
297            }
298            TRANSPOSE => {
299                s.status[j - 1] = Status::Transposed;
300                s.status[j - 2] = Status::Transposed;
301                (i, j) = (i - 2, j - 2);
302            }
303            INSERT => {
304                s.status[j - 1] = Status::Skipped;
305                j -= 1;
306            }
307            _ => i -= 1,
308        }
309    }
310    Ok((end, cells))
311}
312
313/// Highlights `hit` for the query symbols `q`; the entry point of
314/// `Searcher::highlight` and `Searcher::highlight_text`.
315pub(crate) fn run(
316    s: &mut Scratch,
317    trie: &Trie,
318    cm: &CostModel,
319    q: &[u32],
320    hit: &Hit,
321    source: &str,
322    mode: HighlightMode,
323) -> Result<Highlight, HighlightError> {
324    if hit.id as usize >= trie.len() {
325        return Err(HighlightError::UnknownTerm { id: hit.id });
326    }
327    // Without a normaliser the term is stored as given: the identity map.
328    let n = trie.normalizer().unwrap_or(
329        Normalizer::new()
330            .with_case_folding(false)
331            .with_diacritic_folding(false),
332    );
333    let term = n.normalize_mapped(source, &mut s.map);
334    if term != trie.term(hit.id) {
335        return Err(HighlightError::SourceMismatch);
336    }
337    s.t.clear();
338    s.t.extend(term.chars().map(u32::from));
339    let (end, cells) = align(s, cm, q, mode, hit.cost)?;
340    let (ranges, aligned) = source_ranges(source, &s.map, &s.status, end);
341    Ok(Highlight {
342        ranges,
343        aligned,
344        cost: hit.cost,
345        cells,
346    })
347}
348
349/// The highlighted spans of `source`, and the span of its first `end`
350/// normalised symbols, from the status of each normalised symbol.
351///
352/// A source character that produced symbols is highlighted when at least one
353/// of them is, and is aligned when at least one of them is among the first
354/// `end`; one that produced none (a dropped combining mark) takes both states
355/// from the character before it (none at the start of the string).
356fn source_ranges(
357    source: &str,
358    map: &SourceMap,
359    status: &[Status],
360    end: usize,
361) -> (Vec<MatchRange>, MatchRange) {
362    type Pos = (usize, usize, usize);
363    let span = |a: Pos, b: Pos| MatchRange {
364        chars: a.0..b.0,
365        utf8: a.1..b.1,
366        utf16: a.2..b.2,
367    };
368    // (chars, utf8, utf16) at the current position.
369    let mut at: Pos = (0, 0, 0);
370    let mut ranges = Vec::new();
371    let mut open: Option<Pos> = None;
372    let mut aligned: Option<(Pos, Pos)> = None;
373    // Where an empty aligned span sits: the first character with a symbol.
374    let mut first: Option<Pos> = None;
375    let mut p = 0;
376    let (mut lit, mut inside) = (false, false);
377    for (k, ch) in source.chars().enumerate() {
378        let p0 = p;
379        let mut any = false;
380        while map.source_of(p) == Some(k) {
381            any |= status.get(p).is_some_and(|s| s.highlighted());
382            p += 1;
383        }
384        if p > p0 {
385            lit = any;
386            inside = p0 < end;
387            first.get_or_insert(at);
388        }
389        let next = (at.0 + 1, at.1 + ch.len_utf8(), at.2 + ch.len_utf16());
390        if inside {
391            aligned = Some((aligned.map_or(at, |a| a.0), next));
392        }
393        match (lit, open) {
394            (true, None) => open = Some(at),
395            (false, Some(o)) => {
396                ranges.push(span(o, at));
397                open = None;
398            }
399            _ => {}
400        }
401        at = next;
402    }
403    if let Some(o) = open {
404        ranges.push(span(o, at));
405    }
406    let aligned = match aligned {
407        Some((a, b)) => span(a, b),
408        None => {
409            let e = first.unwrap_or(at);
410            span(e, e)
411        }
412    };
413    (ranges, aligned)
414}
415
416#[cfg(test)]
417mod tests {
418    use super::*;
419    use crate::cost::Layout;
420    use crate::search::{SearchConfig, Searcher};
421    use alloc::string::String;
422    use alloc::vec;
423
424    /// Small deterministic xorshift generator.
425    struct Rng(u64);
426
427    impl Rng {
428        fn new(seed: u64) -> Self {
429            Rng(seed.wrapping_mul(0x9E37_79B9_7F4A_7C15) | 1)
430        }
431        fn below(&mut self, n: usize) -> usize {
432            self.0 ^= self.0 << 13;
433            self.0 ^= self.0 >> 7;
434            self.0 ^= self.0 << 17;
435            (self.0 % n as u64) as usize
436        }
437    }
438
439    /// Naive full-matrix weighted OSA, written independently of `moves`:
440    /// `d[j][i]` aligns `t[..j]` with `q[..i]`.
441    fn oracle(cm: &CostModel, q: &[u32], t: &[u32]) -> Vec<Vec<u32>> {
442        const BIG: u32 = 1_000_000;
443        let (m, n) = (q.len(), t.len());
444        let mut d = vec![vec![BIG; m + 1]; n + 1];
445        d[0][0] = 0;
446        for j in 0..=n {
447            for i in 0..=m {
448                let mut best = d[j][i];
449                if i >= 1 && j >= 1 {
450                    best = best
451                        .min(d[j - 1][i - 1] + u32::from(cm.sub_cost(q[i - 1], t[j - 1], i - 1)));
452                }
453                if j >= 1 {
454                    let prev_t = if j >= 2 { Some(t[j - 2]) } else { None };
455                    best = best.min(d[j - 1][i] + u32::from(cm.ins_cost(t[j - 1], prev_t, i)));
456                }
457                if i >= 1 {
458                    best = best.min(d[j][i - 1] + u32::from(cm.del_cost(q, i - 1)));
459                }
460                if i >= 2
461                    && j >= 2
462                    && q[i - 1] == t[j - 2]
463                    && q[i - 2] == t[j - 1]
464                    && q[i - 1] != q[i - 2]
465                {
466                    best = best.min(d[j - 2][i - 2] + u32::from(cm.transpose_cost(i - 2)));
467                }
468                d[j][i] = best;
469            }
470        }
471        d
472    }
473
474    /// The value of each move into `d[j][i]`, in the documented tie order
475    /// (diagonal, transposition, insertion, deletion), computed here from the
476    /// cost model (not through `moves`); `None` if the move is not available.
477    fn candidates(
478        cm: &CostModel,
479        q: &[u32],
480        t: &[u32],
481        d: &[Vec<u32>],
482        i: usize,
483        j: usize,
484    ) -> [Option<u32>; 4] {
485        let mut c = [None; 4];
486        if i >= 1 && j >= 1 {
487            c[0] = Some(d[j - 1][i - 1] + u32::from(cm.sub_cost(q[i - 1], t[j - 1], i - 1)));
488        }
489        if i >= 2 && j >= 2 && q[i - 1] == t[j - 2] && q[i - 2] == t[j - 1] && q[i - 1] != q[i - 2]
490        {
491            c[1] = Some(d[j - 2][i - 2] + u32::from(cm.transpose_cost(i - 2)));
492        }
493        if j >= 1 {
494            let prev = if j >= 2 { Some(t[j - 2]) } else { None };
495            c[2] = Some(d[j - 1][i] + u32::from(cm.ins_cost(t[j - 1], prev, i)));
496        }
497        if i >= 1 {
498            c[3] = Some(d[j][i - 1] + u32::from(cm.del_cost(q, i - 1)));
499        }
500        c
501    }
502
503    /// Checks the walked path against the independent matrix `d`: it is a
504    /// connected walk from its end cell to (0, 0), each step is the first
505    /// move in the documented tie order that attains the cell's value, and
506    /// the step costs sum to the value of the end cell, which is returned.
507    fn check_path(
508        cm: &CostModel,
509        q: &[u32],
510        t: &[u32],
511        d: &[Vec<u32>],
512        path: &[(usize, usize, usize)],
513    ) -> u32 {
514        let mut total = 0u32;
515        let mut expect_at: Option<(usize, usize)> = None;
516        for &(mv, i, j) in path {
517            if let Some(at) = expect_at {
518                assert_eq!(at, (i, j), "path not connected");
519            }
520            let c = candidates(cm, q, t, d, i, j);
521            let order = [SUB, TRANSPOSE, INSERT, DELETE];
522            let first = c.iter().position(|&v| v == Some(d[j][i]));
523            assert_eq!(first.map(|k| order[k]), Some(mv), "tie rule at ({i}, {j})");
524            let (prev, next) = match mv {
525                SUB => (d[j - 1][i - 1], (i - 1, j - 1)),
526                TRANSPOSE => (d[j - 2][i - 2], (i - 2, j - 2)),
527                INSERT => (d[j - 1][i], (i, j - 1)),
528                _ => (d[j][i - 1], (i - 1, j)),
529            };
530            total += d[j][i] - prev;
531            expect_at = Some(next);
532        }
533        assert_eq!(
534            expect_at.unwrap_or((0, 0)),
535            (0, 0),
536            "path does not reach (0, 0)"
537        );
538        total
539    }
540
541    fn syms(s: &str) -> Vec<u32> {
542        s.chars().map(u32::from).collect()
543    }
544
545    const ALPHABETS: [&str; 6] = ["aqw", "asdfqwer", "abcdefghij", "aeéèçß", "жзaЖ😀", "çlp.;"];
546
547    /// For random dictionaries and queries, every hit of both modes is
548    /// highlighted; the path is legal, follows the tie rule, and its step
549    /// costs sum to the hit's cost, which is the oracle cost; the statuses
550    /// agree with the path.
551    #[test]
552    fn traceback_cost_equals_oracle_and_hit_cost() {
553        let rounds = if cfg!(miri) { 3 } else { 120 };
554        let (mut hits, mut prefix_hits, mut transposed, mut skipped) = (0, 0, 0, 0);
555        for (a, alpha) in ALPHABETS.iter().enumerate() {
556            let alpha = syms(alpha);
557            for d in 0..rounds {
558                let mut rng = Rng::new((a as u64 + 1) * 7919 + d);
559                let cm = CostModel::for_layout(Layout::ALL[d as usize % Layout::ALL.len()]);
560                let words: Vec<String> = (0..1 + rng.below(12))
561                    .map(|_| {
562                        (0..1 + rng.below(7))
563                            .map(|_| char::from_u32(alpha[rng.below(alpha.len())]).unwrap_or('a'))
564                            .collect()
565                    })
566                    .collect();
567                let items: Vec<(&str, u16)> = words.iter().map(|w| (w.as_str(), 1)).collect();
568                let Ok(trie) = Trie::build(&items) else {
569                    continue;
570                };
571                let mut s = Searcher::new();
572                for _ in 0..6 {
573                    // A dictionary word with swaps and edits, or random.
574                    let mut q = syms(&words[rng.below(words.len())]);
575                    for _ in 0..rng.below(3) {
576                        match rng.below(3) {
577                            0 if q.len() > 1 => {
578                                let i = rng.below(q.len() - 1);
579                                q.swap(i, i + 1);
580                            }
581                            1 => q.insert(rng.below(q.len() + 1), alpha[rng.below(alpha.len())]),
582                            _ if !q.is_empty() => {
583                                q.remove(rng.below(q.len()));
584                            }
585                            _ => {}
586                        }
587                    }
588                    let qs: String = q.iter().filter_map(|&c| char::from_u32(c)).collect();
589                    let cfg = SearchConfig {
590                        k: 50,
591                        budget: 64,
592                        ..SearchConfig::default()
593                    };
594                    for mode in [HighlightMode::Whole, HighlightMode::Prefix] {
595                        let out = match mode {
596                            HighlightMode::Whole => s.search(&trie, &cm, qs.as_bytes(), &cfg),
597                            _ => s.search_prefix(&trie, &cm, qs.as_bytes(), &cfg),
598                        };
599                        for hit in out.unwrap_or_else(|e| panic!("{e}")).hits {
600                            let term = trie.term(hit.id);
601                            let t = syms(term);
602                            let h = s
603                                .highlight(&trie, &cm, qs.as_bytes(), &hit, term, mode)
604                                .unwrap_or_else(|e| panic!("{e} q={qs:?} t={term:?} {mode:?}"));
605                            let d = oracle(&cm, &q, &t);
606                            let col: Vec<u32> = d.iter().map(|r| r[q.len()]).collect();
607                            let want = match mode {
608                                HighlightMode::Whole => col[t.len()],
609                                _ => col.iter().copied().min().unwrap_or(u32::MAX),
610                            };
611                            assert_eq!(u32::from(h.cost), want);
612                            assert_eq!(h.cost, hit.cost);
613                            let sc = &s.hl;
614                            assert_eq!(
615                                check_path(&cm, &q, &t, &d, &sc.path),
616                                want,
617                                "q={qs:?} t={term:?}"
618                            );
619                            // Statuses follow the path.
620                            for &(mv, i, j) in &sc.path {
621                                match mv {
622                                    SUB if q[i - 1] == t[j - 1] => {
623                                        assert_eq!(sc.status[j - 1], Status::Matched)
624                                    }
625                                    SUB => assert_eq!(sc.status[j - 1], Status::Substituted),
626                                    TRANSPOSE => {
627                                        transposed += 1;
628                                        assert_eq!(sc.status[j - 1], Status::Transposed);
629                                        assert_eq!(sc.status[j - 2], Status::Transposed);
630                                    }
631                                    INSERT => {
632                                        skipped += 1;
633                                        assert_eq!(sc.status[j - 1], Status::Skipped)
634                                    }
635                                    _ => {}
636                                }
637                            }
638                            if mode == HighlightMode::Prefix {
639                                prefix_hits += 1;
640                                // The shortest prefix of minimal cost.
641                                let end = h.aligned.chars.end;
642                                assert_eq!(col.iter().position(|&c| c == want), Some(end));
643                                assert!(sc.status[end..].iter().all(|&x| x == Status::Unaligned));
644                            } else {
645                                hits += 1;
646                                assert!(sc.status.iter().all(|&x| x != Status::Unaligned));
647                            }
648                        }
649                    }
650                }
651            }
652        }
653        std::eprintln!(
654            "{hits} whole-term hits, {prefix_hits} prefix hits, {transposed} transpositions, \
655             {skipped} skipped symbols"
656        );
657        if !cfg!(miri) {
658            assert!(hits > 2_000 && prefix_hits > 2_000 && transposed > 50 && skipped > 500);
659        }
660    }
661
662    /// Among equal-cost alignments, the diagonal move wins at every cell, so
663    /// edits go to the left.
664    #[test]
665    fn ties_put_edits_leftmost() {
666        let cm = CostModel::qwerty();
667        // "abab" against "ab": the two extra query symbols are dropped from
668        // the middle, and both term symbols are matched with the last ones.
669        let mut s = Scratch {
670            t: syms("ab"),
671            ..Scratch::default()
672        };
673        let q = syms("abab");
674        let (end, _) = align(&mut s, &cm, &q, HighlightMode::Whole, 32).unwrap_or((9, 9));
675        assert_eq!(end, 2);
676        assert_eq!(s.status, [Status::Matched, Status::Matched]);
677        let path: Vec<(usize, usize, usize)> = s.path.clone();
678        assert_eq!(
679            path,
680            [(SUB, 4, 2), (DELETE, 3, 1), (DELETE, 2, 1), (SUB, 1, 1)]
681        );
682        // "abcab" against "ab": dropping "cab" or "bca" both cost 48 (dropping
683        // "abc" costs 56, the first symbol weighs x1.5). The rule keeps the
684        // last "b" and drops "bca".
685        let q = syms("abcab");
686        let (_, _) = align(&mut s, &cm, &q, HighlightMode::Whole, 48).unwrap_or((9, 9));
687        assert_eq!(s.status, [Status::Matched, Status::Matched]);
688        assert_eq!(s.path.first(), Some(&(SUB, 5, 2)));
689        assert_eq!(s.path.last(), Some(&(SUB, 1, 1)));
690    }
691
692    #[test]
693    fn impossible_costs_are_refused_before_any_work() {
694        let cm = CostModel::qwerty();
695        let mut s = Scratch {
696            t: syms("abcdefghijklmnop"),
697            ..Scratch::default()
698        };
699        let q = syms("a");
700        for mode in [HighlightMode::Whole, HighlightMode::Prefix] {
701            assert_eq!(
702                align(&mut s, &cm, &q, mode, 65),
703                Err(HighlightError::CostMismatch {
704                    expected: 65,
705                    found: None
706                })
707            );
708        }
709        // Fifteen insertions cannot cost 64.
710        assert_eq!(
711            align(&mut s, &cm, &q, HighlightMode::Whole, 64),
712            Err(HighlightError::CostMismatch {
713                expected: 64,
714                found: None
715            })
716        );
717        // In prefix mode the matrix stops at m + cost / 8 term symbols: two
718        // rows of two cells for cost 0, ten rows for cost 64.
719        assert_eq!(
720            align(&mut s, &cm, &q, HighlightMode::Prefix, 0),
721            Ok((1, 2 * 2))
722        );
723        assert_eq!(
724            align(&mut s, &cm, &q, HighlightMode::Prefix, 64),
725            Err(HighlightError::CostMismatch {
726                expected: 64,
727                found: Some(0)
728            })
729        );
730    }
731}
keyhammer/highlight.rs

keyhammer/
highlight.rs
