diff options
| -rw-r--r-- | Changelog.md | 1 | ||||
| -rw-r--r-- | libdevcore/StringUtils.cpp | 101 | ||||
| -rw-r--r-- | libdevcore/StringUtils.h | 39 | ||||
| -rw-r--r-- | libsolidity/analysis/DeclarationContainer.cpp | 22 | ||||
| -rw-r--r-- | libsolidity/analysis/DeclarationContainer.h | 4 | ||||
| -rw-r--r-- | libsolidity/analysis/NameAndTypeResolver.cpp | 6 | ||||
| -rw-r--r-- | libsolidity/analysis/NameAndTypeResolver.h | 3 | ||||
| -rw-r--r-- | libsolidity/analysis/ReferencesResolver.cpp | 8 | ||||
| -rw-r--r-- | test/libdevcore/StringUtils.cpp | 88 | ||||
| -rw-r--r-- | test/libsolidity/SolidityNameAndTypeResolution.cpp | 87 |
10 files changed, 357 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/libdevcore/StringUtils.cpp b/libdevcore/StringUtils.cpp new file mode 100644 index 00000000..2ff86bd5 --- /dev/null +++ b/libdevcore/StringUtils.cpp @@ -0,0 +1,101 @@ +/* + 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 <http://www.gnu.org/licenses/>. +*/ +/** @file StringUtils.h + * @author Balajiganapathi S <balajiganapathi.s@gmail.com> + * @date 2017 + * + * String routines + */ + +#include "StringUtils.h" +#include <algorithm> +#include <string> +#include <vector> + +using namespace std; +using namespace dev; + +bool dev::stringWithinDistance(string const& _str1, string const& _str2, size_t _maxDistance) +{ + if (_str1 == _str2) + return true; + + 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; +} + +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 + // This is a two-dimensional array of size 3 x (n2 + 1). + vector<size_t> 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 + for (size_t i1 = 0; i1 <= n1; ++i1) + for (size_t i2 = 0; i2 <= n2; ++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 * 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]) + // same chars, can skip + x = min(x, upleft); + else + // 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) * 3] + 1); + } + dp[(i1 % 3) + i2 * 3] = x; + } + + return dp[(n1 % 3) + n2 * 3]; +} + +string dev::quotedAlternativesList(vector<string> 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 new file mode 100644 index 00000000..acd93e32 --- /dev/null +++ b/libdevcore/StringUtils.h @@ -0,0 +1,39 @@ +/* + 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 <http://www.gnu.org/licenses/>. +*/ +/** @file StringUtils.h + * @author Balajiganapathi S <balajiganapathi.s@gmail.com> + * @date 2017 + * + * String routines + */ + +#pragma once + +#include <string> +#include <vector> + +namespace dev +{ + +// 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<std::string> const& suggestions); + +} diff --git a/libsolidity/analysis/DeclarationContainer.cpp b/libsolidity/analysis/DeclarationContainer.cpp index b33c8568..7508ad9e 100644 --- a/libsolidity/analysis/DeclarationContainer.cpp +++ b/libsolidity/analysis/DeclarationContainer.cpp @@ -23,6 +23,7 @@ #include <libsolidity/analysis/DeclarationContainer.h> #include <libsolidity/ast/AST.h> #include <libsolidity/ast/Types.h> +#include <libdevcore/StringUtils.h> using namespace std; using namespace dev; @@ -105,7 +106,7 @@ bool DeclarationContainer::registerDeclaration( return true; } -std::vector<Declaration const*> DeclarationContainer::resolveName(ASTString const& _name, bool _recursive) const +vector<Declaration const*> DeclarationContainer::resolveName(ASTString const& _name, bool _recursive) const { solAssert(!_name.empty(), "Attempt to resolve empty name."); auto result = m_declarations.find(_name); @@ -115,3 +116,22 @@ std::vector<Declaration const*> DeclarationContainer::resolveName(ASTString cons return m_enclosingContainer->resolveName(_name, true); return vector<Declaration const*>({}); } + +vector<ASTString> DeclarationContainer::similarNames(ASTString const& _name) const +{ + static size_t const MAXIMUM_EDIT_DISTANCE = 2; + + vector<ASTString> similar; + + for (auto const& declaration: m_declarations) + { + string const& declarationName = declaration.first; + if (stringWithinDistance(_name, declarationName, MAXIMUM_EDIT_DISTANCE)) + similar.push_back(declarationName); + } + + if (m_enclosingContainer) + similar += m_enclosingContainer->similarNames(_name); + + return similar; +} diff --git a/libsolidity/analysis/DeclarationContainer.h b/libsolidity/analysis/DeclarationContainer.h index 301998b7..f9b1bda4 100644 --- a/libsolidity/analysis/DeclarationContainer.h +++ b/libsolidity/analysis/DeclarationContainer.h @@ -58,6 +58,10 @@ 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. + /// Searches this and all parent containers. + std::vector<ASTString> similarNames(ASTString const& _name) const; + private: ASTNode const* m_enclosingNode; DeclarationContainer const* m_enclosingContainer; diff --git a/libsolidity/analysis/NameAndTypeResolver.cpp b/libsolidity/analysis/NameAndTypeResolver.cpp index 5d010693..5e4d414b 100644 --- a/libsolidity/analysis/NameAndTypeResolver.cpp +++ b/libsolidity/analysis/NameAndTypeResolver.cpp @@ -25,6 +25,7 @@ #include <libsolidity/ast/AST.h> #include <libsolidity/analysis/TypeChecker.h> #include <libsolidity/interface/ErrorReporter.h> +#include <libdevcore/StringUtils.h> #include <boost/algorithm/string.hpp> @@ -425,6 +426,11 @@ vector<_T const*> NameAndTypeResolver::cThreeMerge(list<list<_T const*>>& _toMer return result; } +string NameAndTypeResolver::similarNameSuggestions(ASTString const& _name) const +{ + return quotedAlternativesList(m_currentScope->similarNames(_name)); +} + DeclarationRegistrationHelper::DeclarationRegistrationHelper( map<ASTNode const*, shared_ptr<DeclarationContainer>>& _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..0bb5e3fe 100644 --- a/libsolidity/analysis/ReferencesResolver.cpp +++ b/libsolidity/analysis/ReferencesResolver.cpp @@ -47,7 +47,13 @@ bool ReferencesResolver::visit(Identifier const& _identifier) { auto declarations = m_resolver.nameFromCurrentScope(_identifier.name()); if (declarations.empty()) - declarationError(_identifier.location(), "Undeclared identifier."); + { + 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) _identifier.annotation().referencedDeclaration = declarations.front(); else diff --git a/test/libdevcore/StringUtils.cpp b/test/libdevcore/StringUtils.cpp new file mode 100644 index 00000000..597457cc --- /dev/null +++ b/test/libdevcore/StringUtils.cpp @@ -0,0 +1,88 @@ +/* + 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 <http://www.gnu.org/licenses/>. +*/ +/** + * Unit tests for the StringUtils routines. + */ + +#include <libdevcore/StringUtils.h> + +#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_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<string> 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() + +} +} diff --git a/test/libsolidity/SolidityNameAndTypeResolution.cpp b/test/libsolidity/SolidityNameAndTypeResolution.cpp index e757c755..c4741657 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"( |