From 2859834e58e37e7b15a15f7df60feef3e1527c97 Mon Sep 17 00:00:00 2001 From: Balajiganapathi S Date: Sun, 29 Oct 2017 13:38:40 +0530 Subject: Suggest alternatives when identifier not found. --- Changelog.md | 1 + libsolidity/analysis/DeclarationContainer.cpp | 63 +++++++++++++++- libsolidity/analysis/DeclarationContainer.h | 8 ++ libsolidity/analysis/NameAndTypeResolver.cpp | 17 +++++ libsolidity/analysis/NameAndTypeResolver.h | 3 + libsolidity/analysis/ReferencesResolver.cpp | 6 +- test/libsolidity/SolidityNameAndTypeResolution.cpp | 87 ++++++++++++++++++++++ 7 files changed, 183 insertions(+), 2 deletions(-) diff --git a/Changelog.md b/Changelog.md index ab1b35cd..1b4149a5 100644 --- a/Changelog.md +++ b/Changelog.md @@ -8,6 +8,7 @@ Features: * Inline Assembly: Issue warning for using jump labels (already existed for jump instructions). * Inline Assembly: Support some restricted tokens (return, byte, address) as identifiers in Julia mode. * Optimiser: Replace `x % 2**i` by `x & (2**i-1)`. + * Resolver: Suggest alternative identifiers if a given identifier is not found. * SMT Checker: If-else branch conditions are taken into account in the SMT encoding of the program variables. * Syntax Checker: Deprecate the ``var`` keyword (and mark it an error as experimental 0.5.0 feature). diff --git a/libsolidity/analysis/DeclarationContainer.cpp b/libsolidity/analysis/DeclarationContainer.cpp index b33c8568..d41bc7d3 100644 --- a/libsolidity/analysis/DeclarationContainer.cpp +++ b/libsolidity/analysis/DeclarationContainer.cpp @@ -105,7 +105,7 @@ bool DeclarationContainer::registerDeclaration( return true; } -std::vector DeclarationContainer::resolveName(ASTString const& _name, bool _recursive) const +vector DeclarationContainer::resolveName(ASTString const& _name, bool _recursive) const { solAssert(!_name.empty(), "Attempt to resolve empty name."); auto result = m_declarations.find(_name); @@ -115,3 +115,64 @@ std::vector DeclarationContainer::resolveName(ASTString cons return m_enclosingContainer->resolveName(_name, true); return vector({}); } + +vector DeclarationContainer::similarNames(ASTString const& _name) const +{ + vector similar; + + for (auto const& declaration: m_declarations) + { + string const& declarationName = declaration.first; + if (DeclarationContainer::areSimilarNames(_name, declarationName)) + similar.push_back(declarationName); + } + + if (m_enclosingContainer) + { + vector enclosingSimilar = m_enclosingContainer->similarNames(_name); + similar.insert(similar.end(), enclosingSimilar.begin(), enclosingSimilar.end()); + } + + return similar; +} + +bool DeclarationContainer::areSimilarNames(ASTString const& _name1, ASTString const& _name2) +{ + if (_name1 == _name2) + return true; + + size_t n1 = _name1.size(), n2 = _name2.size(); + vector> dp(n1 + 1, vector(n2 + 1)); + + // In this dp formulation of Damerau–Levenshtein distance we are assuming that the strings are 1-based to make base case storage easier. + // So index accesser to _name1 and _name2 have to be adjusted accordingly + for (size_t i1 = 0; i1 <= n1; ++i1) + { + for (size_t i2 = 0; i2 <= n2; ++i2) + { + if (min(i1, i2) == 0) // base case + dp[i1][i2] = max(i1, i2); + else + { + dp[i1][i2] = min(dp[i1-1][i2] + 1, dp[i1][i2-1] + 1); + // Deletion and insertion + if (_name1[i1-1] == _name2[i2-1]) + // Same chars, can skip + dp[i1][i2] = min(dp[i1][i2], dp[i1-1][i2-1]); + else + // Different chars so try substitution + dp[i1][i2] = min(dp[i1][i2], dp[i1-1][i2-1] + 1); + + if (i1 > 1 && i2 > 1 && _name1[i1-1] == _name2[i2-2] && _name1[i1-2] == _name2[i2-1]) + // Try transposing + dp[i1][i2] = min(dp[i1][i2], dp[i1-2][i2-2] + 1); + } + } + } + + size_t distance = dp[n1][n2]; + + // If distance is not greater than MAXIMUM_DISTANCE, and distance is strictly less than length of both names, + // they can be considered similar this is to avoid irrelevant suggestions + return distance <= MAXIMUM_DISTANCE && distance < n1 && distance < n2; +} diff --git a/libsolidity/analysis/DeclarationContainer.h b/libsolidity/analysis/DeclarationContainer.h index 301998b7..991140d8 100644 --- a/libsolidity/analysis/DeclarationContainer.h +++ b/libsolidity/analysis/DeclarationContainer.h @@ -58,11 +58,19 @@ public: /// @returns whether declaration is valid, and if not also returns previous declaration. Declaration const* conflictingDeclaration(Declaration const& _declaration, ASTString const* _name = nullptr) const; + /// @returns existing declaration names similar to @a _name. + std::vector similarNames(ASTString const& _name) const; + + private: ASTNode const* m_enclosingNode; DeclarationContainer const* m_enclosingContainer; std::map> m_declarations; std::map> m_invisibleDeclarations; + + // Calculates the Damerau–Levenshtein distance and decides whether the two names are similar + static bool areSimilarNames(ASTString const& _name1, ASTString const& _name2); + static size_t const MAXIMUM_DISTANCE = 2; }; } diff --git a/libsolidity/analysis/NameAndTypeResolver.cpp b/libsolidity/analysis/NameAndTypeResolver.cpp index 5d010693..a9a62529 100644 --- a/libsolidity/analysis/NameAndTypeResolver.cpp +++ b/libsolidity/analysis/NameAndTypeResolver.cpp @@ -425,6 +425,23 @@ vector<_T const*> NameAndTypeResolver::cThreeMerge(list>& _toMer return result; } +string NameAndTypeResolver::similarNameSuggestions(ASTString const& _name) const +{ + vector suggestions = m_currentScope->similarNames(_name); + if (suggestions.empty()) + return ""; + if (suggestions.size() == 1) + return suggestions.front(); + + string choices = suggestions.front(); + for (size_t i = 1; i + 1 < suggestions.size(); ++i) + choices += ", " + suggestions[i]; + + choices += " or " + suggestions.back(); + + return choices; +} + DeclarationRegistrationHelper::DeclarationRegistrationHelper( map>& _scopes, ASTNode& _astRoot, diff --git a/libsolidity/analysis/NameAndTypeResolver.h b/libsolidity/analysis/NameAndTypeResolver.h index d83697cd..9aea07ab 100644 --- a/libsolidity/analysis/NameAndTypeResolver.h +++ b/libsolidity/analysis/NameAndTypeResolver.h @@ -93,6 +93,9 @@ public: /// Generate and store warnings about variables that are named like instructions. void warnVariablesNamedLikeInstructions(); + /// @returns a list of similar identifiers in the current and enclosing scopes. May return empty string if no suggestions. + std::string similarNameSuggestions(ASTString const& _name) const; + private: /// Internal version of @a resolveNamesAndTypes (called from there) throws exceptions on fatal errors. bool resolveNamesAndTypesInternal(ASTNode& _node, bool _resolveInsideCode = true); diff --git a/libsolidity/analysis/ReferencesResolver.cpp b/libsolidity/analysis/ReferencesResolver.cpp index 451d6c93..1b0e8179 100644 --- a/libsolidity/analysis/ReferencesResolver.cpp +++ b/libsolidity/analysis/ReferencesResolver.cpp @@ -47,7 +47,11 @@ bool ReferencesResolver::visit(Identifier const& _identifier) { auto declarations = m_resolver.nameFromCurrentScope(_identifier.name()); if (declarations.empty()) - declarationError(_identifier.location(), "Undeclared identifier."); + { + string const& suggestions = m_resolver.similarNameSuggestions(_identifier.name()); + string errorMessage = "Undeclared identifier." + (suggestions.empty()? "": " Did you mean " + suggestions + "?"); + declarationError(_identifier.location(), errorMessage); + } else if (declarations.size() == 1) _identifier.annotation().referencedDeclaration = declarations.front(); else diff --git a/test/libsolidity/SolidityNameAndTypeResolution.cpp b/test/libsolidity/SolidityNameAndTypeResolution.cpp index e757c755..51d81a28 100644 --- a/test/libsolidity/SolidityNameAndTypeResolution.cpp +++ b/test/libsolidity/SolidityNameAndTypeResolution.cpp @@ -2081,6 +2081,93 @@ BOOST_AUTO_TEST_CASE(external_visibility) CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier."); } +BOOST_AUTO_TEST_CASE(similar_name_suggestions_expected) +{ + char const* sourceCode = R"( + contract c { + function func() {} + function g() public { fun(); } + } + )"; + CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier. Did you mean func?"); +} + +BOOST_AUTO_TEST_CASE(no_name_suggestion) +{ + char const* sourceCode = R"( + contract c { + function g() public { fun(); } + } + )"; + CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier."); +} + +BOOST_AUTO_TEST_CASE(multiple_similar_suggestions) +{ + char const* sourceCode = R"( + contract c { + function g() public { + uint var1 = 1; + uint var2 = 1; + uint var3 = 1; + uint var4 = 1; + uint var5 = varx; + } + } + )"; + CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier. Did you mean var1, var2, var3, var4 or var5?"); +} + +BOOST_AUTO_TEST_CASE(multiple_scopes_suggestions) +{ + char const* sourceCode = R"( + contract c { + uint log9 = 2; + function g() public { + uint log8 = 3; + uint var1 = lgox; + } + } + )"; + CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier. Did you mean log8, log9, log0, log1, log2, log3 or log4?"); +} + +BOOST_AUTO_TEST_CASE(inheritence_suggestions) +{ + char const* sourceCode = R"( + contract a { function func() public {} } + contract c is a { + function g() public { + uint var1 = fun(); + } + } + )"; + CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier. Did you mean func?"); +} + +BOOST_AUTO_TEST_CASE(no_spurious_suggestions) +{ + char const* sourceCode = R"( + contract c { + function g() public { + uint va = 1; + uint vb = vaxyz; + } + } + )"; + CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier."); + + sourceCode = R"( + contract c { + function g() public { + uint va = 1; + uint vb = x; + } + } + )"; + CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier."); +} + BOOST_AUTO_TEST_CASE(external_base_visibility) { char const* sourceCode = R"( -- cgit From b1417b318f3b3cbfd0bf79a4cabc656825a84e5a Mon Sep 17 00:00:00 2001 From: Balajiganapathi S Date: Fri, 17 Nov 2017 21:41:15 +0530 Subject: Move string distance function to utils and format error message --- libdevcore/StringUtils.cpp | 77 ++++++++++++++++++++++ libdevcore/StringUtils.h | 35 ++++++++++ libsolidity/analysis/DeclarationContainer.cpp | 44 +------------ libsolidity/analysis/DeclarationContainer.h | 2 - libsolidity/analysis/NameAndTypeResolver.cpp | 8 +-- test/libsolidity/SolidityNameAndTypeResolution.cpp | 8 +-- 6 files changed, 122 insertions(+), 52 deletions(-) create mode 100644 libdevcore/StringUtils.cpp create mode 100644 libdevcore/StringUtils.h diff --git a/libdevcore/StringUtils.cpp b/libdevcore/StringUtils.cpp new file mode 100644 index 00000000..7b2b4f5e --- /dev/null +++ b/libdevcore/StringUtils.cpp @@ -0,0 +1,77 @@ +/* + This file is part of solidity. + + solidity is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + solidity is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with solidity. If not, see . +*/ +/** @file StringUtils.h + * @author Balajiganapathi S + * @date 2017 + * + * String routines + */ + +#include "StringUtils.h" +#include +#include +#include + +using namespace std; +using namespace dev; + +namespace dev +{ + +bool stringWithinDistance(string const& _name1, string const& _name2, size_t _maxDistance) +{ + if (_name1 == _name2) + return true; + + size_t n1 = _name1.size(), n2 = _name2.size(); + vector> dp(n1 + 1, vector(n2 + 1)); + + // In this dp formulation of Damerau–Levenshtein distance we are assuming that the strings are 1-based to make base case storage easier. + // So index accesser to _name1 and _name2 have to be adjusted accordingly + for (size_t i1 = 0; i1 <= n1; ++i1) + { + for (size_t i2 = 0; i2 <= n2; ++i2) + { + if (min(i1, i2) == 0) + // Base case + dp[i1][i2] = max(i1, i2); + else + { + dp[i1][i2] = min(dp[i1 - 1][i2] + 1, dp[i1][i2 - 1] + 1); + // Deletion and insertion + if (_name1[i1 - 1] == _name2[i2 - 1]) + // Same chars, can skip + dp[i1][i2] = min(dp[i1][i2], dp[i1 - 1][i2 - 1]); + else + // Different chars so try substitution + dp[i1][i2] = min(dp[i1][i2], dp[i1 - 1][i2 - 1] + 1); + + if (i1 > 1 && i2 > 1 && _name1[i1 - 1] == _name2[i2 - 2] && _name1[i1 - 2] == _name2[i2 - 1]) + // Try transposing + dp[i1][i2] = min(dp[i1][i2], dp[i1 - 2][i2 - 2] + 1); + } + } + } + + size_t distance = dp[n1][n2]; + + // if distance is not greater than _maxDistance, and distance is strictly less than length of both names, + // they can be considered similar this is to avoid irrelevant suggestions + return distance <= _maxDistance && distance < n1 && distance < n2; +} + +} diff --git a/libdevcore/StringUtils.h b/libdevcore/StringUtils.h new file mode 100644 index 00000000..d3f9f8d9 --- /dev/null +++ b/libdevcore/StringUtils.h @@ -0,0 +1,35 @@ +/* + This file is part of solidity. + + solidity is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + solidity is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with solidity. If not, see . +*/ +/** @file StringUtils.h + * @author Balajiganapathi S + * @date 2017 + * + * String routines + */ + +#pragma once + +#include + +namespace dev +{ + +/// Calculates the Damerau–Levenshtein distance between @a _name1 and @a _name2 and +/// @returns true if that distance is not greater than @a _maxDistance +bool stringWithinDistance(std::string const& _name1, std::string const& _name2, size_t _maxDistance); + +} diff --git a/libsolidity/analysis/DeclarationContainer.cpp b/libsolidity/analysis/DeclarationContainer.cpp index d41bc7d3..f9a52dc6 100644 --- a/libsolidity/analysis/DeclarationContainer.cpp +++ b/libsolidity/analysis/DeclarationContainer.cpp @@ -23,6 +23,7 @@ #include #include #include +#include using namespace std; using namespace dev; @@ -123,7 +124,7 @@ vector DeclarationContainer::similarNames(ASTString const& _name) con for (auto const& declaration: m_declarations) { string const& declarationName = declaration.first; - if (DeclarationContainer::areSimilarNames(_name, declarationName)) + if (stringWithinDistance(_name, declarationName, MAXIMUM_DISTANCE)) similar.push_back(declarationName); } @@ -135,44 +136,3 @@ vector DeclarationContainer::similarNames(ASTString const& _name) con return similar; } - -bool DeclarationContainer::areSimilarNames(ASTString const& _name1, ASTString const& _name2) -{ - if (_name1 == _name2) - return true; - - size_t n1 = _name1.size(), n2 = _name2.size(); - vector> dp(n1 + 1, vector(n2 + 1)); - - // In this dp formulation of Damerau–Levenshtein distance we are assuming that the strings are 1-based to make base case storage easier. - // So index accesser to _name1 and _name2 have to be adjusted accordingly - for (size_t i1 = 0; i1 <= n1; ++i1) - { - for (size_t i2 = 0; i2 <= n2; ++i2) - { - if (min(i1, i2) == 0) // base case - dp[i1][i2] = max(i1, i2); - else - { - dp[i1][i2] = min(dp[i1-1][i2] + 1, dp[i1][i2-1] + 1); - // Deletion and insertion - if (_name1[i1-1] == _name2[i2-1]) - // Same chars, can skip - dp[i1][i2] = min(dp[i1][i2], dp[i1-1][i2-1]); - else - // Different chars so try substitution - dp[i1][i2] = min(dp[i1][i2], dp[i1-1][i2-1] + 1); - - if (i1 > 1 && i2 > 1 && _name1[i1-1] == _name2[i2-2] && _name1[i1-2] == _name2[i2-1]) - // Try transposing - dp[i1][i2] = min(dp[i1][i2], dp[i1-2][i2-2] + 1); - } - } - } - - size_t distance = dp[n1][n2]; - - // If distance is not greater than MAXIMUM_DISTANCE, and distance is strictly less than length of both names, - // they can be considered similar this is to avoid irrelevant suggestions - return distance <= MAXIMUM_DISTANCE && distance < n1 && distance < n2; -} diff --git a/libsolidity/analysis/DeclarationContainer.h b/libsolidity/analysis/DeclarationContainer.h index 991140d8..6c1459c7 100644 --- a/libsolidity/analysis/DeclarationContainer.h +++ b/libsolidity/analysis/DeclarationContainer.h @@ -68,8 +68,6 @@ private: std::map> m_declarations; std::map> m_invisibleDeclarations; - // Calculates the Damerau–Levenshtein distance and decides whether the two names are similar - static bool areSimilarNames(ASTString const& _name1, ASTString const& _name2); static size_t const MAXIMUM_DISTANCE = 2; }; diff --git a/libsolidity/analysis/NameAndTypeResolver.cpp b/libsolidity/analysis/NameAndTypeResolver.cpp index a9a62529..21f2af5f 100644 --- a/libsolidity/analysis/NameAndTypeResolver.cpp +++ b/libsolidity/analysis/NameAndTypeResolver.cpp @@ -431,13 +431,13 @@ string NameAndTypeResolver::similarNameSuggestions(ASTString const& _name) const if (suggestions.empty()) return ""; if (suggestions.size() == 1) - return suggestions.front(); + return "\"" + suggestions.front() + "\""; - string choices = suggestions.front(); + string choices = "\"" + suggestions.front() + "\""; for (size_t i = 1; i + 1 < suggestions.size(); ++i) - choices += ", " + suggestions[i]; + choices += ", \"" + suggestions[i] + "\""; - choices += " or " + suggestions.back(); + choices += " or \"" + suggestions.back() + "\""; return choices; } diff --git a/test/libsolidity/SolidityNameAndTypeResolution.cpp b/test/libsolidity/SolidityNameAndTypeResolution.cpp index 51d81a28..c4741657 100644 --- a/test/libsolidity/SolidityNameAndTypeResolution.cpp +++ b/test/libsolidity/SolidityNameAndTypeResolution.cpp @@ -2089,7 +2089,7 @@ BOOST_AUTO_TEST_CASE(similar_name_suggestions_expected) function g() public { fun(); } } )"; - CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier. Did you mean func?"); + CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier. Did you mean \"func\"?"); } BOOST_AUTO_TEST_CASE(no_name_suggestion) @@ -2115,7 +2115,7 @@ BOOST_AUTO_TEST_CASE(multiple_similar_suggestions) } } )"; - CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier. Did you mean var1, var2, var3, var4 or var5?"); + CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier. Did you mean \"var1\", \"var2\", \"var3\", \"var4\" or \"var5\"?"); } BOOST_AUTO_TEST_CASE(multiple_scopes_suggestions) @@ -2129,7 +2129,7 @@ BOOST_AUTO_TEST_CASE(multiple_scopes_suggestions) } } )"; - CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier. Did you mean log8, log9, log0, log1, log2, log3 or log4?"); + CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier. Did you mean \"log8\", \"log9\", \"log0\", \"log1\", \"log2\", \"log3\" or \"log4\"?"); } BOOST_AUTO_TEST_CASE(inheritence_suggestions) @@ -2142,7 +2142,7 @@ BOOST_AUTO_TEST_CASE(inheritence_suggestions) } } )"; - CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier. Did you mean func?"); + CHECK_ERROR(sourceCode, DeclarationError, "Undeclared identifier. Did you mean \"func\"?"); } BOOST_AUTO_TEST_CASE(no_spurious_suggestions) -- cgit From d123e777d33be3134ebbcda969f149e0e7ad0b0f Mon Sep 17 00:00:00 2001 From: Balajiganapathi S Date: Sat, 18 Nov 2017 12:24:17 +0530 Subject: Add tests for similarity routine --- test/libdevcore/StringUtils.cpp | 56 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 56 insertions(+) create mode 100644 test/libdevcore/StringUtils.cpp diff --git a/test/libdevcore/StringUtils.cpp b/test/libdevcore/StringUtils.cpp new file mode 100644 index 00000000..7a5fe26e --- /dev/null +++ b/test/libdevcore/StringUtils.cpp @@ -0,0 +1,56 @@ +/* + This file is part of solidity. + + solidity is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + solidity is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with solidity. If not, see . +*/ +/** + * Unit tests for the StringUtils routines. + */ + +#include + +#include "../TestHelper.h" + +using namespace std; + +namespace dev +{ +namespace test +{ + +BOOST_AUTO_TEST_SUITE(StringUtils) + +BOOST_AUTO_TEST_CASE(test_similarity) +{ + BOOST_CHECK_EQUAL(stringWithinDistance("hello", "hello", 0), true); + BOOST_CHECK_EQUAL(stringWithinDistance("hello", "hello", 1), true); + BOOST_CHECK_EQUAL(stringWithinDistance("hello", "hellw", 1), true); + BOOST_CHECK_EQUAL(stringWithinDistance("hello", "helol", 1), true); + BOOST_CHECK_EQUAL(stringWithinDistance("hello", "helo", 1), true); + BOOST_CHECK_EQUAL(stringWithinDistance("hello", "helllo", 1), true); + BOOST_CHECK_EQUAL(stringWithinDistance("hello", "hlllo", 1), true); + BOOST_CHECK_EQUAL(stringWithinDistance("hello", "hllllo", 1), false); + BOOST_CHECK_EQUAL(stringWithinDistance("hello", "hllllo", 2), true); + BOOST_CHECK_EQUAL(stringWithinDistance("hello", "hlllo", 2), true); + BOOST_CHECK_EQUAL(stringWithinDistance("a", "", 2), false); + BOOST_CHECK_EQUAL(stringWithinDistance("abc", "ba", 2), false); + BOOST_CHECK_EQUAL(stringWithinDistance("abc", "abcdef", 2), false); + BOOST_CHECK_EQUAL(stringWithinDistance("abcd", "wxyz", 2), false); + BOOST_CHECK_EQUAL(stringWithinDistance("", "", 2), true); +} + +BOOST_AUTO_TEST_SUITE_END() + +} +} -- cgit From 8a491c77ba9680afdf8c33664e905b978152b095 Mon Sep 17 00:00:00 2001 From: Balajiganapathi S Date: Tue, 21 Nov 2017 22:20:35 +0530 Subject: Restructure code for alternative identifier suggestions --- libdevcore/StringUtils.cpp | 69 ++++++++++++++++----------- libdevcore/StringUtils.h | 10 ++-- libsolidity/analysis/DeclarationContainer.cpp | 9 ++-- libsolidity/analysis/DeclarationContainer.h | 1 - libsolidity/analysis/NameAndTypeResolver.cpp | 15 +----- test/libdevcore/StringUtils.cpp | 32 +++++++++++++ 6 files changed, 86 insertions(+), 50 deletions(-) diff --git a/libdevcore/StringUtils.cpp b/libdevcore/StringUtils.cpp index 7b2b4f5e..1dbe151f 100644 --- a/libdevcore/StringUtils.cpp +++ b/libdevcore/StringUtils.cpp @@ -29,16 +29,24 @@ using namespace std; using namespace dev; -namespace dev +bool dev::stringWithinDistance(string const& _str1, string const& _str2, size_t _maxDistance) { - -bool stringWithinDistance(string const& _name1, string const& _name2, size_t _maxDistance) -{ - if (_name1 == _name2) + if (_str1 == _str2) return true; - size_t n1 = _name1.size(), n2 = _name2.size(); - vector> dp(n1 + 1, vector(n2 + 1)); + size_t n1 = _str1.size(), n2 = _str2.size(); + size_t distance = stringDistance(_str1, _str2); + + // if distance is not greater than _maxDistance, and distance is strictly less than length of both names, they can be considered similar + // this is to avoid irrelevant suggestions + return distance <= _maxDistance && distance < n1 && distance < n2; +} + +size_t dev::stringDistance(string const& _str1, string const& _str2) +{ + size_t n1 = _str1.size(), n2 = _str2.size(); + // Optimize by storing only last 2 rows and current row. So first index is considered modulo 3 + vector> dp(3, vector(n2 + 1)); // In this dp formulation of Damerau–Levenshtein distance we are assuming that the strings are 1-based to make base case storage easier. // So index accesser to _name1 and _name2 have to be adjusted accordingly @@ -46,32 +54,37 @@ bool stringWithinDistance(string const& _name1, string const& _name2, size_t _ma { for (size_t i2 = 0; i2 <= n2; ++i2) { - if (min(i1, i2) == 0) - // Base case - dp[i1][i2] = max(i1, i2); - else - { - dp[i1][i2] = min(dp[i1 - 1][i2] + 1, dp[i1][i2 - 1] + 1); - // Deletion and insertion - if (_name1[i1 - 1] == _name2[i2 - 1]) - // Same chars, can skip - dp[i1][i2] = min(dp[i1][i2], dp[i1 - 1][i2 - 1]); + if (min(i1, i2) == 0) // base case + dp[i1 % 3][i2] = max(i1, i2); else - // Different chars so try substitution - dp[i1][i2] = min(dp[i1][i2], dp[i1 - 1][i2 - 1] + 1); + { + dp[i1 % 3][i2] = min(dp[(i1-1) % 3][i2] + 1, dp[i1 % 3][i2-1] + 1); // deletion and insertion + if (_str1[i1-1] == _str2[i2-1]) // same chars, can skip + dp[i1 % 3][i2] = min(dp[i1 % 3][i2], dp[(i1-1) % 3][i2-1]); + else // different chars so try substitution + dp[i1 % 3][i2] = min(dp[i1 % 3][i2], dp[(i1-1) % 3][i2-1] + 1); - if (i1 > 1 && i2 > 1 && _name1[i1 - 1] == _name2[i2 - 2] && _name1[i1 - 2] == _name2[i2 - 1]) - // Try transposing - dp[i1][i2] = min(dp[i1][i2], dp[i1 - 2][i2 - 2] + 1); - } + if (i1 > 1 && i2 > 1 && _str1[i1-1] == _str2[i2-2] && _str1[i1-2] == _str2[i2-1]) // Try transposing + dp[i1 % 3][i2] = min(dp[i1 % 3][i2], dp[(i1-2) % 3][i2-2] + 1); + } } } - size_t distance = dp[n1][n2]; - - // if distance is not greater than _maxDistance, and distance is strictly less than length of both names, - // they can be considered similar this is to avoid irrelevant suggestions - return distance <= _maxDistance && distance < n1 && distance < n2; + return dp[n1 % 3][n2]; } +string dev::quotedAlternativesList(vector const& suggestions) { + if (suggestions.empty()) + return ""; + if (suggestions.size() == 1) + return "\"" + suggestions.front() + "\""; + + string choices = "\"" + suggestions.front() + "\""; + for (size_t i = 1; i + 1 < suggestions.size(); ++i) + choices += ", \"" + suggestions[i] + "\""; + + choices += " or \"" + suggestions.back() + "\""; + + return choices; } + diff --git a/libdevcore/StringUtils.h b/libdevcore/StringUtils.h index d3f9f8d9..acd93e32 100644 --- a/libdevcore/StringUtils.h +++ b/libdevcore/StringUtils.h @@ -24,12 +24,16 @@ #pragma once #include +#include namespace dev { -/// Calculates the Damerau–Levenshtein distance between @a _name1 and @a _name2 and -/// @returns true if that distance is not greater than @a _maxDistance -bool stringWithinDistance(std::string const& _name1, std::string const& _name2, size_t _maxDistance); +// Calculates the Damerau–Levenshtein distance between _str1 and _str2 and returns true if that distance is not greater than _maxDistance +bool stringWithinDistance(std::string const& _str1, std::string const& _str2, size_t _maxDistance); +// Calculates the Damerau–Levenshtein distance between _str1 and _str2 +size_t stringDistance(std::string const& _str1, std::string const& _str2); +// Return a string having elements of suggestions as quoted, alternative suggestions. e.g. "a", "b" or "c" +std::string quotedAlternativesList(std::vector const& suggestions); } diff --git a/libsolidity/analysis/DeclarationContainer.cpp b/libsolidity/analysis/DeclarationContainer.cpp index f9a52dc6..7508ad9e 100644 --- a/libsolidity/analysis/DeclarationContainer.cpp +++ b/libsolidity/analysis/DeclarationContainer.cpp @@ -119,20 +119,19 @@ vector DeclarationContainer::resolveName(ASTString const& _n vector DeclarationContainer::similarNames(ASTString const& _name) const { + static size_t const MAXIMUM_EDIT_DISTANCE = 2; + vector similar; for (auto const& declaration: m_declarations) { string const& declarationName = declaration.first; - if (stringWithinDistance(_name, declarationName, MAXIMUM_DISTANCE)) + if (stringWithinDistance(_name, declarationName, MAXIMUM_EDIT_DISTANCE)) similar.push_back(declarationName); } if (m_enclosingContainer) - { - vector enclosingSimilar = m_enclosingContainer->similarNames(_name); - similar.insert(similar.end(), enclosingSimilar.begin(), enclosingSimilar.end()); - } + similar += m_enclosingContainer->similarNames(_name); return similar; } diff --git a/libsolidity/analysis/DeclarationContainer.h b/libsolidity/analysis/DeclarationContainer.h index 6c1459c7..94bbe129 100644 --- a/libsolidity/analysis/DeclarationContainer.h +++ b/libsolidity/analysis/DeclarationContainer.h @@ -68,7 +68,6 @@ private: std::map> m_declarations; std::map> m_invisibleDeclarations; - static size_t const MAXIMUM_DISTANCE = 2; }; } diff --git a/libsolidity/analysis/NameAndTypeResolver.cpp b/libsolidity/analysis/NameAndTypeResolver.cpp index 21f2af5f..5e4d414b 100644 --- a/libsolidity/analysis/NameAndTypeResolver.cpp +++ b/libsolidity/analysis/NameAndTypeResolver.cpp @@ -25,6 +25,7 @@ #include #include #include +#include #include @@ -427,19 +428,7 @@ vector<_T const*> NameAndTypeResolver::cThreeMerge(list>& _toMer string NameAndTypeResolver::similarNameSuggestions(ASTString const& _name) const { - vector suggestions = m_currentScope->similarNames(_name); - if (suggestions.empty()) - return ""; - if (suggestions.size() == 1) - return "\"" + suggestions.front() + "\""; - - string choices = "\"" + suggestions.front() + "\""; - for (size_t i = 1; i + 1 < suggestions.size(); ++i) - choices += ", \"" + suggestions[i] + "\""; - - choices += " or \"" + suggestions.back() + "\""; - - return choices; + return quotedAlternativesList(m_currentScope->similarNames(_name)); } DeclarationRegistrationHelper::DeclarationRegistrationHelper( diff --git a/test/libdevcore/StringUtils.cpp b/test/libdevcore/StringUtils.cpp index 7a5fe26e..597457cc 100644 --- a/test/libdevcore/StringUtils.cpp +++ b/test/libdevcore/StringUtils.cpp @@ -50,6 +50,38 @@ BOOST_AUTO_TEST_CASE(test_similarity) BOOST_CHECK_EQUAL(stringWithinDistance("", "", 2), true); } +BOOST_AUTO_TEST_CASE(test_dldistance) +{ + BOOST_CHECK_EQUAL(stringDistance("hello", "hellw"), 1); + BOOST_CHECK_EQUAL(stringDistance("hello", "helol"), 1); + BOOST_CHECK_EQUAL(stringDistance("hello", "helo"), 1); + BOOST_CHECK_EQUAL(stringDistance("hello", "helllo"), 1); + BOOST_CHECK_EQUAL(stringDistance("hello", "hlllo"), 1); + BOOST_CHECK_EQUAL(stringDistance("hello", "hllllo"), 2); + BOOST_CHECK_EQUAL(stringDistance("a", ""), 1); + BOOST_CHECK_EQUAL(stringDistance("abc", "ba"), 2); + BOOST_CHECK_EQUAL(stringDistance("abc", "abcdef"), 3); + BOOST_CHECK_EQUAL(stringDistance("abcd", "wxyz"), 4); + BOOST_CHECK_EQUAL(stringDistance("", ""), 0); + BOOST_CHECK_EQUAL(stringDistance("abcdefghijklmnopqrstuvwxyz", "abcabcabcabcabcabcabcabca"), 23); + +} + +BOOST_AUTO_TEST_CASE(test_alternatives_list) +{ + vector strings; + BOOST_CHECK_EQUAL(quotedAlternativesList(strings), ""); + strings.push_back("a"); + BOOST_CHECK_EQUAL(quotedAlternativesList(strings), "\"a\""); + strings.push_back("b"); + BOOST_CHECK_EQUAL(quotedAlternativesList(strings), "\"a\" or \"b\""); + strings.push_back("c"); + BOOST_CHECK_EQUAL(quotedAlternativesList(strings), "\"a\", \"b\" or \"c\""); + strings.push_back("d"); + BOOST_CHECK_EQUAL(quotedAlternativesList(strings), "\"a\", \"b\", \"c\" or \"d\""); +} + + BOOST_AUTO_TEST_SUITE_END() } -- cgit From dc0a25f1cdd0fe8a8de3a8a9a8376fc77e8de213 Mon Sep 17 00:00:00 2001 From: chriseth Date: Fri, 9 Feb 2018 17:45:45 +0100 Subject: Minor changes. --- libdevcore/StringUtils.cpp | 11 +++++++---- libsolidity/analysis/DeclarationContainer.h | 3 +-- 2 files changed, 8 insertions(+), 6 deletions(-) diff --git a/libdevcore/StringUtils.cpp b/libdevcore/StringUtils.cpp index 1dbe151f..3bdf71f5 100644 --- a/libdevcore/StringUtils.cpp +++ b/libdevcore/StringUtils.cpp @@ -34,17 +34,19 @@ bool dev::stringWithinDistance(string const& _str1, string const& _str2, size_t if (_str1 == _str2) return true; - size_t n1 = _str1.size(), n2 = _str2.size(); + size_t n1 = _str1.size(); + size_t n2 = _str2.size(); size_t distance = stringDistance(_str1, _str2); // if distance is not greater than _maxDistance, and distance is strictly less than length of both names, they can be considered similar // this is to avoid irrelevant suggestions - return distance <= _maxDistance && distance < n1 && distance < n2; + return distance <= _maxDistance && distance < n1 && distance < n2; } size_t dev::stringDistance(string const& _str1, string const& _str2) { - size_t n1 = _str1.size(), n2 = _str2.size(); + size_t n1 = _str1.size(); + size_t n2 = _str2.size(); // Optimize by storing only last 2 rows and current row. So first index is considered modulo 3 vector> dp(3, vector(n2 + 1)); @@ -73,7 +75,8 @@ size_t dev::stringDistance(string const& _str1, string const& _str2) return dp[n1 % 3][n2]; } -string dev::quotedAlternativesList(vector const& suggestions) { +string dev::quotedAlternativesList(vector const& suggestions) +{ if (suggestions.empty()) return ""; if (suggestions.size() == 1) diff --git a/libsolidity/analysis/DeclarationContainer.h b/libsolidity/analysis/DeclarationContainer.h index 94bbe129..f9b1bda4 100644 --- a/libsolidity/analysis/DeclarationContainer.h +++ b/libsolidity/analysis/DeclarationContainer.h @@ -59,15 +59,14 @@ public: Declaration const* conflictingDeclaration(Declaration const& _declaration, ASTString const* _name = nullptr) const; /// @returns existing declaration names similar to @a _name. + /// Searches this and all parent containers. std::vector similarNames(ASTString const& _name) const; - private: ASTNode const* m_enclosingNode; DeclarationContainer const* m_enclosingContainer; std::map> m_declarations; std::map> m_invisibleDeclarations; - }; } -- cgit From 12c3eb8880bd6c50b5fd0aad76626fcce4f663b5 Mon Sep 17 00:00:00 2001 From: chriseth Date: Fri, 9 Feb 2018 17:49:50 +0100 Subject: Suggestion to improve readability. --- libdevcore/StringUtils.cpp | 35 +++++++++++++++++++++-------------- 1 file changed, 21 insertions(+), 14 deletions(-) diff --git a/libdevcore/StringUtils.cpp b/libdevcore/StringUtils.cpp index 3bdf71f5..c4b1d5a9 100644 --- a/libdevcore/StringUtils.cpp +++ b/libdevcore/StringUtils.cpp @@ -53,24 +53,31 @@ size_t dev::stringDistance(string const& _str1, string const& _str2) // In this dp formulation of Damerau–Levenshtein distance we are assuming that the strings are 1-based to make base case storage easier. // So index accesser to _name1 and _name2 have to be adjusted accordingly for (size_t i1 = 0; i1 <= n1; ++i1) - { for (size_t i2 = 0; i2 <= n2; ++i2) { - if (min(i1, i2) == 0) // base case - dp[i1 % 3][i2] = max(i1, i2); + size_t x = 0; + if (min(i1, i2) == 0) // base case + x = max(i1, i2); + else + { + size_t left = dp[(i1-1) % 3][i2]; + size_t up = dp[i1 % 3][i2-1]; + size_t upleft = dp[(i1 - 1) % 3][i2-1]; + // deletion and insertion + x = min(left + 1, up + 1); + if (_str1[i1-1] == _str2[i2-1]) + // same chars, can skip + x = min(x, upleft); else - { - dp[i1 % 3][i2] = min(dp[(i1-1) % 3][i2] + 1, dp[i1 % 3][i2-1] + 1); // deletion and insertion - if (_str1[i1-1] == _str2[i2-1]) // same chars, can skip - dp[i1 % 3][i2] = min(dp[i1 % 3][i2], dp[(i1-1) % 3][i2-1]); - else // different chars so try substitution - dp[i1 % 3][i2] = min(dp[i1 % 3][i2], dp[(i1-1) % 3][i2-1] + 1); - - if (i1 > 1 && i2 > 1 && _str1[i1-1] == _str2[i2-2] && _str1[i1-2] == _str2[i2-1]) // Try transposing - dp[i1 % 3][i2] = min(dp[i1 % 3][i2], dp[(i1-2) % 3][i2-2] + 1); - } + // different chars so try substitution + x = min(x, upleft + 1); + + // transposing + if (i1 > 1 && i2 > 1 && _str1[i1 - 1] == _str2[i2 - 2] && _str1[i1 - 2] == _str2[i2 - 1]) + x = min(x, dp[(i1 - 2) % 3][i2 - 2] + 1); + } + dp[i1 % 3][i2] = x; } - } return dp[n1 % 3][n2]; } -- cgit From 5747985e6a272edd512d53b2da438577fe461bb6 Mon Sep 17 00:00:00 2001 From: chriseth Date: Fri, 9 Feb 2018 17:53:30 +0100 Subject: Use one-dimensional vector. --- libdevcore/StringUtils.cpp | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-) diff --git a/libdevcore/StringUtils.cpp b/libdevcore/StringUtils.cpp index c4b1d5a9..2ff86bd5 100644 --- a/libdevcore/StringUtils.cpp +++ b/libdevcore/StringUtils.cpp @@ -48,7 +48,8 @@ size_t dev::stringDistance(string const& _str1, string const& _str2) size_t n1 = _str1.size(); size_t n2 = _str2.size(); // Optimize by storing only last 2 rows and current row. So first index is considered modulo 3 - vector> dp(3, vector(n2 + 1)); + // This is a two-dimensional array of size 3 x (n2 + 1). + vector dp(3 * (n2 + 1)); // In this dp formulation of Damerau–Levenshtein distance we are assuming that the strings are 1-based to make base case storage easier. // So index accesser to _name1 and _name2 have to be adjusted accordingly @@ -60,9 +61,9 @@ size_t dev::stringDistance(string const& _str1, string const& _str2) x = max(i1, i2); else { - size_t left = dp[(i1-1) % 3][i2]; - size_t up = dp[i1 % 3][i2-1]; - size_t upleft = dp[(i1 - 1) % 3][i2-1]; + size_t left = dp[(i1 - 1) % 3 + i2 * 3]; + size_t up = dp[(i1 % 3) + (i2 - 1) * 3]; + size_t upleft = dp[((i1 - 1) % 3) + (i2 - 1) * 3]; // deletion and insertion x = min(left + 1, up + 1); if (_str1[i1-1] == _str2[i2-1]) @@ -74,12 +75,12 @@ size_t dev::stringDistance(string const& _str1, string const& _str2) // transposing if (i1 > 1 && i2 > 1 && _str1[i1 - 1] == _str2[i2 - 2] && _str1[i1 - 2] == _str2[i2 - 1]) - x = min(x, dp[(i1 - 2) % 3][i2 - 2] + 1); + x = min(x, dp[((i1 - 2) % 3) + (i2 - 2) * 3] + 1); } - dp[i1 % 3][i2] = x; + dp[(i1 % 3) + i2 * 3] = x; } - return dp[n1 % 3][n2]; + return dp[(n1 % 3) + n2 * 3]; } string dev::quotedAlternativesList(vector const& suggestions) -- cgit From 1dcd7c5e0b249511dca34dff0507b432db3bf7d1 Mon Sep 17 00:00:00 2001 From: chriseth Date: Fri, 9 Feb 2018 17:58:50 +0100 Subject: Fix: remove reference. --- libsolidity/analysis/ReferencesResolver.cpp | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/libsolidity/analysis/ReferencesResolver.cpp b/libsolidity/analysis/ReferencesResolver.cpp index 1b0e8179..0bb5e3fe 100644 --- a/libsolidity/analysis/ReferencesResolver.cpp +++ b/libsolidity/analysis/ReferencesResolver.cpp @@ -48,8 +48,10 @@ bool ReferencesResolver::visit(Identifier const& _identifier) auto declarations = m_resolver.nameFromCurrentScope(_identifier.name()); if (declarations.empty()) { - string const& suggestions = m_resolver.similarNameSuggestions(_identifier.name()); - string errorMessage = "Undeclared identifier." + (suggestions.empty()? "": " Did you mean " + suggestions + "?"); + string suggestions = m_resolver.similarNameSuggestions(_identifier.name()); + string errorMessage = + "Undeclared identifier." + + (suggestions.empty()? "": " Did you mean " + std::move(suggestions) + "?"); declarationError(_identifier.location(), errorMessage); } else if (declarations.size() == 1) -- cgit