Introduce a limit to Levenshtein distance computation#93325
Introduce a limit to Levenshtein distance computation#93325bors merged 3 commits intorust-lang:masterfrom
Conversation
Incorporate distance limit from `find_best_match_for_name` directly into Levenshtein distance computation. Use the string size difference as a lower bound on the distance and exit early when it exceeds the specified limit. After finding a candidate within a limit, lower the limit further to restrict the search space.
|
r? @davidtwco (rust-highfive has picked a reviewer for you, use r? to override) |
davidtwco
left a comment
There was a problem hiding this comment.
Changes look good to me, let's check the perf difference before we land though :)
|
@bors try @rust-timer queue |
|
Awaiting bors try build completion. @rustbot label: +S-waiting-on-perf |
|
⌛ Trying commit 6236882 with merge ec5c9fcc826d0b99e53d90c553c7957777ea98d8... |
|
☀️ Try build successful - checks-actions |
|
Queued ec5c9fcc826d0b99e53d90c553c7957777ea98d8 with parent 563250a, future comparison URL. |
|
Finished benchmarking commit (ec5c9fcc826d0b99e53d90c553c7957777ea98d8): comparison url. Summary: This benchmark run did not return any relevant results. 1 results were found to be statistically significant but too small to be relevant. If you disagree with this performance assessment, please file an issue in rust-lang/rustc-perf. Benchmarking this pull request likely means that it is perf-sensitive, so we're automatically marking it as not fit for rolling up. While you can manually mark this PR as fit for rollup, we strongly recommend not doing so since this PR led to changes in compiler perf. @bors rollup=never |
|
@bors r+ rollup |
|
📌 Commit 6236882 has been approved by |
…askrgr Rollup of 8 pull requests Successful merges: - rust-lang#91641 (Define c_char using cfg_if rather than repeating 40-line cfg) - rust-lang#92899 (Mention std::iter::zip in Iterator::zip docs) - rust-lang#93193 (Add test for stable hash uniqueness of adjacent field values) - rust-lang#93325 (Introduce a limit to Levenshtein distance computation) - rust-lang#93339 (rustdoc: add test case for multiple traits and erased names) - rust-lang#93357 (Clarify the `usage-of-qualified-ty` error message.) - rust-lang#93363 (`#[rustc_pass_by_value]` cleanup) - rust-lang#93365 (More arena cleanups) Failed merges: r? `@ghost` `@rustbot` modify labels: rollup
Incorporate distance limit from
find_best_match_for_namedirectly intoLevenshtein distance computation.
Use the string size difference as a lower bound on the distance and exit
early when it exceeds the specified limit.
After finding a candidate within a limit, lower the limit further to
restrict the search space.