Use a Levenshtein calculating algorithm with a threshold.

Use a Levenshtein calculating algorithm with a threshold.

R=paulberry@google.com
BUG=

Committed: https://code.google.com/p/dart/source/detail?r=38591

[Paul Berry, 2014-07-25 19:53:26]

lgtm, assuming the off by one semantic difference is fixed.

https://codereview.chromium.org/417263003/diff/1/pkg/analysis_services/lib/sr...
File pkg/analysis_services/lib/src/correction/fix.dart (right):

https://codereview.chromium.org/417263003/diff/1/pkg/analysis_services/lib/sr...
pkg/analysis_services/lib/src/correction/fix.dart:1051: if (finder._element !=
null) {
I think this introduces an unintentional off-by-one semantic change. 
Previously, we only accepted elements whose edit distance was *less than* 5.  We
now accept elements whose edit distance is *less than or equal to* 5.

https://codereview.chromium.org/417263003/diff/1/pkg/analysis_services/lib/sr...
File pkg/analysis_services/lib/src/correction/levenshtein.dart (right):

https://codereview.chromium.org/417263003/diff/1/pkg/analysis_services/lib/sr...
pkg/analysis_services/lib/src/correction/levenshtein.dart:39: int m = t.length;
Minor nit: can we swap the meanings of n and m?  I keep expecting m = s.length
and n = t.length because of alphabetical order.

Or alternatively, rename to something like s_len and t_len.

https://codereview.chromium.org/417263003/diff/1/pkg/analysis_services/lib/sr...
pkg/analysis_services/lib/src/correction/levenshtein.dart:48: 
The Levenshtein distance can never be less than abs(m - n), so it's probably
worth adding a check like:

if ((m - n).abs() > threshold) {
  return LEVENSHTEIN_MAX;
}

[scheglov, 2014-07-25 21:18:24]

https://codereview.chromium.org/417263003/diff/1/pkg/analysis_services/lib/sr...
File pkg/analysis_services/lib/src/correction/fix.dart (right):

https://codereview.chromium.org/417263003/diff/1/pkg/analysis_services/lib/sr...
pkg/analysis_services/lib/src/correction/fix.dart:1051: if (finder._element !=
null) {
On 2014/07/25 19:53:26, Paul Berry wrote:
> I think this introduces an unintentional off-by-one semantic change. 
> Previously, we only accepted elements whose edit distance was *less than* 5. 
We
> now accept elements whose edit distance is *less than or equal to* 5.

Done.

https://codereview.chromium.org/417263003/diff/1/pkg/analysis_services/lib/sr...
File pkg/analysis_services/lib/src/correction/levenshtein.dart (right):

https://codereview.chromium.org/417263003/diff/1/pkg/analysis_services/lib/sr...
pkg/analysis_services/lib/src/correction/levenshtein.dart:39: int m = t.length;
On 2014/07/25 19:53:26, Paul Berry wrote:
> Minor nit: can we swap the meanings of n and m?  I keep expecting m = s.length
> and n = t.length because of alphabetical order.
> 
> Or alternatively, rename to something like s_len and t_len.

Done.

https://codereview.chromium.org/417263003/diff/1/pkg/analysis_services/lib/sr...
pkg/analysis_services/lib/src/correction/levenshtein.dart:48: 
On 2014/07/25 19:53:26, Paul Berry wrote:
> The Levenshtein distance can never be less than abs(m - n), so it's probably
> worth adding a check like:
> 
> if ((m - n).abs() > threshold) {
>   return LEVENSHTEIN_MAX;
> }

Done.

[scheglov, 2014-07-25 21:18:39]

Committed patchset #2 manually as r38591 (presubmit successful).