mz_deploy/
suggest.rs

1// Copyright Materialize, Inc. and contributors. All rights reserved.
2//
3// Use of this software is governed by the Business Source License
4// included in the LICENSE file.
5//
6// As of the Change Date specified in that file, in accordance with
7// the Business Source License, use of this software will be governed
8// by the Apache License, Version 2.0.
9
10//! Nearest-name suggestions for names that did not resolve.
11//!
12//! Shared by the LSP's quick fixes and the deployment validation errors so a
13//! misspelling reads the same however the user hit it.
14
15/// Maximum number of suggestions returned by [`did_you_mean`].
16pub(crate) const MAX_DID_YOU_MEAN: usize = 3;
17
18/// Return up to [`MAX_DID_YOU_MEAN`] closest names from `candidates` to
19/// `needle`, sorted by Damerau-Levenshtein distance ascending. Names whose
20/// distance exceeds `max(2, needle.len() / 3)` are filtered out so unrelated
21/// matches don't surface as suggestions.
22///
23/// Allocations only happen for surviving candidates, so passing a borrowed
24/// slice (e.g. `pool.iter()`) is cheap even when the pool has thousands of
25/// names.
26pub(crate) fn did_you_mean<I, S>(needle: &str, candidates: I) -> Vec<String>
27where
28    I: IntoIterator<Item = S>,
29    S: AsRef<str>,
30{
31    let threshold = std::cmp::max(2, needle.len() / 3);
32    let mut scored: Vec<(usize, String)> = candidates
33        .into_iter()
34        .filter_map(|c| {
35            let s = c.as_ref();
36            let d = strsim::damerau_levenshtein(needle, s);
37            (d <= threshold).then(|| (d, s.to_string()))
38        })
39        .collect();
40    scored.sort_by_key(|(d, _)| *d);
41    scored.truncate(MAX_DID_YOU_MEAN);
42    scored.into_iter().map(|(_, s)| s).collect()
43}
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48
49    #[mz_ore::test]
50    fn did_you_mean_returns_empty_for_no_close_match() {
51        let candidates = ["customer_name", "customer_id", "shipping_address"];
52        let out = did_you_mean("xyz", candidates.iter().map(|s| s.to_string()));
53        assert!(out.is_empty(), "expected no matches, got {:?}", out);
54    }
55
56    #[mz_ore::test]
57    fn did_you_mean_returns_exact_match_first() {
58        let candidates = ["customer_name", "customer_id"];
59        let out = did_you_mean("customer_name", candidates.iter().map(|s| s.to_string()));
60        // "customer_name" (distance 0) and "customer_id" (distance 4) are both within
61        // threshold max(2, 13/3) = 4, so both are returned, sorted by distance.
62        assert_eq!(
63            out,
64            vec!["customer_name".to_string(), "customer_id".to_string()]
65        );
66    }
67
68    #[mz_ore::test]
69    fn did_you_mean_handles_transposition() {
70        // Damerau-Levenshtein treats one transposition as distance 1.
71        let candidates = ["customer_name"];
72        let out = did_you_mean("cusotmer_name", candidates.iter().map(|s| s.to_string()));
73        assert_eq!(out, vec!["customer_name".to_string()]);
74    }
75
76    #[mz_ore::test]
77    fn did_you_mean_respects_max_three_limit() {
78        // Provide many candidates that are all close enough to hit the limit.
79        // "custoser_name" (distance 1 to): customer_name, custumer_name, cust_name, etc.
80        let candidates = [
81            "customer_name",   // distance 1
82            "custumer_name",   // distance 1 (typo: transposition)
83            "custoser_name_x", // distance 2 (one extra char)
84            "customers",       // distance 6 (exceeds threshold, excluded)
85            "x_custoser_name", // distance 2 (one extra char prefix)
86        ];
87        let out = did_you_mean("custoser_name", candidates.iter().map(|s| s.to_string()));
88        // Should return at most 3, even though multiple candidates match.
89        assert!(out.len() <= 3, "should cap at 3, got {:?}", out);
90        // Best match (distance 1) comes first.
91        assert_eq!(out[0], "customer_name");
92    }
93
94    #[mz_ore::test]
95    fn did_you_mean_skips_empty_candidates() {
96        let candidates: Vec<String> = Vec::new();
97        let out = did_you_mean("anything", candidates);
98        assert!(out.is_empty());
99    }
100}
mz_deploy/suggest.rs

mz_deploy/
suggest.rs
