alpm_lint/
utils.rs

1/// Trait for calculating edit distance between two types.
2pub(crate) trait EditDistance {
3    /// Calculate edit distance between `self` and `other`.
4    fn edit_distance(&self, other: &Self) -> usize;
5}
6
7impl EditDistance for &[u8] {
8    /// Calculate edit distance between `self` and `other` using the Levenshtein distance algorithm.
9    // TODO(cleanup): Investigate the arithmetic_side_effects and indexing_slicing
10    #[expect(clippy::arithmetic_side_effects, clippy::indexing_slicing)]
11    fn edit_distance(&self, other: &Self) -> usize {
12        let mut dp = vec![vec![0; other.len() + 1]; self.len() + 1];
13
14        for i in 0..=self.len() {
15            for j in 0..=other.len() {
16                if i == 0 {
17                    dp[i][j] = j;
18                } else if j == 0 {
19                    dp[i][j] = i;
20                } else if self[i - 1] == other[j - 1] {
21                    dp[i][j] = dp[i - 1][j - 1];
22                } else {
23                    dp[i][j] = 1 + dp[i - 1][j - 1].min(dp[i - 1][j]).min(dp[i][j - 1]);
24                }
25            }
26        }
27
28        dp[self.len()][other.len()]
29    }
30}
31
32impl EditDistance for String {
33    /// Calculate edit distance between `self` and `other`.
34    ///
35    /// Delegates to the byte slice implementation.
36    fn edit_distance(&self, other: &Self) -> usize {
37        self.as_bytes().edit_distance(&other.as_bytes())
38    }
39}
40
41impl EditDistance for &str {
42    /// Calculate edit distance between `self` and `other`.
43    ///
44    /// Delegates to the byte slice implementation.
45    fn edit_distance(&self, other: &Self) -> usize {
46        self.as_bytes().edit_distance(&other.as_bytes())
47    }
48}
49
50#[cfg(test)]
51mod tests {
52    use rstest::rstest;
53
54    use super::*;
55
56    #[rstest]
57    #[case("kitten", "sitting", 3)]
58    #[case("flaw", "lawn", 2)]
59    #[case("intention", "execution", 5)]
60    #[case("", "", 0)]
61    #[case("a", "", 1)]
62    #[case("", "a", 1)]
63    fn test_edit_distance(#[case] s1: &str, #[case] s2: &str, #[case] expected: usize) {
64        let distance = s1.edit_distance(&s2);
65        assert_eq!(distance, expected);
66    }
67}
alpm_lint/utils.rs

alpm_lint/
utils.rs
