| FazBrowse GitHub Viewer | Trending | | Home |
| Tools: [Download Repo ZIP] [Original HTTPS Page] |
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| Expand Up | @@ -466,9 +466,6 @@ impl fmt::Display for UnicodeEscapeCodepoint { | |
| } | ||
|
|
||
| pub mod levenshtein { | ||
| use core::cell::RefCell; | ||
| use std::thread_local; | ||
|
|
||
| pub const MOVE_COST: usize = 2; | ||
| const CASE_COST: usize = 1; | ||
| const MAX_STRING_SIZE: usize = 40; | ||
| Expand All | @@ -490,13 +487,6 @@ pub mod levenshtein { | |
| } | ||
|
|
||
| pub fn levenshtein_distance(a: &[u8], b: &[u8], max_cost: usize) -> usize { | ||
| thread_local! { | ||
| #[allow(clippy::declare_interior_mutable_const, reason = "thread-local scratch buffer uses const initializer with RefCell")] | ||
| static BUFFER: RefCell<[usize; MAX_STRING_SIZE]> = const { | ||
| RefCell::new([0usize; MAX_STRING_SIZE]) | ||
| }; | ||
| } | ||
|
|
||
| if a == b { | ||
| return 0; | ||
| } | ||
| Expand Down Expand Up | @@ -535,33 +525,33 @@ pub mod levenshtein { | |
| return max_cost + 1; | ||
| } | ||
|
|
||
| BUFFER.with_borrow_mut(|buffer| { | ||
| for (i, x) in buffer.iter_mut().take(a_end).enumerate() { | ||
| *x = (i + 1) * MOVE_COST; | ||
| } | ||
| let mut buffer = [0usize; MAX_STRING_SIZE]; | ||
|
|
||
| let mut result = 0usize; | ||
| for (b_index, b_code) in b_bytes[b_begin..(b_begin + b_end)].iter().enumerate() { | ||
| result = b_index * MOVE_COST; | ||
| let mut distance = result; | ||
| let mut minimum = usize::MAX; | ||
| for (a_index, a_code) in a_bytes[a_begin..(a_begin + a_end)].iter().enumerate() { | ||
| let substitute = distance + substitution_cost(*b_code, *a_code); | ||
| distance = buffer[a_index]; | ||
| let insert_delete = usize::min(result, distance) + MOVE_COST; | ||
| result = usize::min(insert_delete, substitute); | ||
|
|
||
| buffer[a_index] = result; | ||
| if result < minimum { | ||
| minimum = result; | ||
| } | ||
| } | ||
| if minimum > max_cost { | ||
| return max_cost + 1; | ||
| for (i, x) in buffer.iter_mut().take(a_end).enumerate() { | ||
| *x = (i + 1) * MOVE_COST; | ||
| } | ||
|
|
||
| let mut result = 0usize; | ||
| for (b_index, b_code) in b_bytes[b_begin..(b_begin + b_end)].iter().enumerate() { | ||
| result = b_index * MOVE_COST; | ||
|
Comment thread
Copy link
Copy Markdown
Contributor
There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality⚠️ Potential issue | 🔴 Critical 🧩 Analysis chain🏁 Script executed: #!/bin/bash
# Read the levenshtein_distance function around line 536
cat -n crates/common/src/str.rs | sed -n '500,560p'Repository: RustPython/RustPython Length of output: 2483 🏁 Script executed: #!/bin/bash
# Search for test cases related to levenshtein_distance
rg -n 'levenshtein_distance|#\[test\]' crates/common/src/str.rs -A 5 -B 1Repository: RustPython/RustPython Length of output: 474 🏁 Script executed: #!/bin/bash
# Look for any other occurrences of the pattern to understand the refactoring
git log --oneline -n 20 -- crates/common/src/str.rsRepository: RustPython/RustPython Length of output: 93 🏁 Script executed: #!/bin/bash
# Search for any test cases that verify levenshtein distance behavior
find . -name "*.rs" -type f -exec grep -l "levenshtein" {} \;Repository: RustPython/RustPython Length of output: 121 🏁 Script executed: #!/bin/bash
# Look for test cases in the file itself
grep -n "test" crates/common/src/str.rs | head -20Repository: RustPython/RustPython Length of output: 143 🏁 Script executed: #!/bin/bash
# Try to find CPython's implementation online or in comments
rg -n "CPython|suggestions\.c|UTF8_Edit" crates/ -A 3 -B 1Repository: RustPython/RustPython Length of output: 50380 🏁 Script executed: #!/bin/bash
# Check if there's a git history we can inspect for this function
cd crates/common && git log --oneline -n 30 -- src/str.rs 2>/dev/null || echo "Git history not available"Repository: RustPython/RustPython Length of output: 93 🏁 Script executed: #!/bin/bash
# Check the suggestion.rs file which might have the levenshtein implementation
cat -n crates/vm/src/suggestion.rs | head -100Repository: RustPython/RustPython Length of output: 4334 🏁 Script executed: #!/bin/bash
# Search for any tests that use levenshtein_distance or suggestion functionality
find . -name "*.rs" -type f | xargs grep -l "suggestion\|levenshtein" | head -10Repository: RustPython/RustPython Length of output: 324 🏁 Script executed: #!/bin/bash
# Look at the suggestion.rs file to see if it uses the levenshtein_distance function
rg -n "levenshtein_distance" crates/vm/src/suggestion.rs -B 3 -A 3Repository: RustPython/RustPython Length of output: 542 🏁 Script executed: #!/bin/bash
# Search for any tests that call levenshtein_distance or validate its output
find . -name "*.rs" -type f | xargs grep -l "test.*levenshtein\|levenshtein.*test" 2>/dev/nullRepository: RustPython/RustPython Length of output: 49 🏁 Script executed: #!/bin/bash
# Look for any Python tests that might indirectly test levenshtein via suggestions
find . -name "test*.py" -o -name "*test.py" | xargs grep -l "AttributeError\|NameError\|suggestion" 2>/dev/null | head -5Repository: RustPython/RustPython Length of output: 214 🏁 Script executed: #!/bin/bash
# Search for CPython reference or comments about the levenshtein implementation
rg -n "CPython|edit.*cost|levenshtein" crates/common/src/str.rs -B 2 -A 2Repository: RustPython/RustPython Length of output: 329 🌐 Web query: CPython _Py_UTF8_Edit_Cost implementation Levenshtein 💡 Result: In CPython, _Py_UTF8_Edit_Cost() is implemented in Python/suggestions.c and is a bounded, weighted Levenshtein-distance routine over the strings’ UTF-8 byte sequences (it calls PyUnicode_AsUTF8AndSize() for both inputs). [1] Key details of the implementation:
The function is declared as an internal API in Include/internal/pycore_pyerrors.h. [2] Sources: Python/suggestions.c (Android git mirror of CPython) [1]; pycore_pyerrors.h declaration [2]. Line 536: Off-by-one bug in Levenshtein DP initialization. The variable result represents the left-edge cost (deletion cost) for the current DP row. For row b_index+1, this should be (b_index + 1) * MOVE_COST, not b_index * MOVE_COST. The current code computes all edit distances with the wrong row-edge values, producing incorrect results. This matches CPython's _Py_UTF8_Edit_Cost implementation, which correctly uses (b_index + 1) * MOVE_COST. Change line 536 from: result = b_index * MOVE_COST;to: result = (b_index + 1) * MOVE_COST;In `@crates/common/src/str.rs` at line 536, The left-edge initialization in the Levenshtein DP loop is off by one: update the assignment that sets result for the current row (using variables result, b_index, and constant MOVE_COST inside the DP routine) so that it uses (b_index + 1) multiplied by MOVE_COST instead of b_index multiplied by MOVE_COST, ensuring the row deletion cost corresponds to row b_index+1.
Sorry, something went wrong.
All reactions
|
||
| let mut distance = result; | ||
| let mut minimum = usize::MAX; | ||
| for (a_index, a_code) in a_bytes[a_begin..(a_begin + a_end)].iter().enumerate() { | ||
| let substitute = distance + substitution_cost(*b_code, *a_code); | ||
| distance = buffer[a_index]; | ||
| let insert_delete = usize::min(result, distance) + MOVE_COST; | ||
| result = usize::min(insert_delete, substitute); | ||
|
|
||
| buffer[a_index] = result; | ||
| if result < minimum { | ||
| minimum = result; | ||
| } | ||
| } | ||
| result | ||
| }) | ||
| if minimum > max_cost { | ||
| return max_cost + 1; | ||
| } | ||
| } | ||
| result | ||
| } | ||
| } | ||
|
|
||
| Expand Down | ||
| Back | FazBrowse Home | New Git URL |
Uh oh!
There was an error while loading. Please reload this page.