From 3fa8829845bf55df812f81356a3ec43149836bb5 Mon Sep 17 00:00:00 2001 From: bakaoh Date: Fri, 10 Aug 2018 17:31:19 +0700 Subject: Fixes #4718: High CPU usage when using large variable names --- Changelog.md | 1 + libdevcore/StringUtils.cpp | 5 ++++- libdevcore/StringUtils.h | 3 ++- libsolidity/analysis/DeclarationContainer.cpp | 7 +++++-- test/libdevcore/StringUtils.cpp | 1 + .../573_similar_name_longer_than_80_not_suggested.sol | 7 +++++++ .../574_similar_name_shorter_than_80_suggested.sol | 7 +++++++ 7 files changed, 27 insertions(+), 4 deletions(-) create mode 100644 test/libsolidity/syntaxTests/nameAndTypeResolution/573_similar_name_longer_than_80_not_suggested.sol create mode 100644 test/libsolidity/syntaxTests/nameAndTypeResolution/574_similar_name_shorter_than_80_suggested.sol diff --git a/Changelog.md b/Changelog.md index 8a16d900..4fcaad4d 100644 --- a/Changelog.md +++ b/Changelog.md @@ -98,6 +98,7 @@ Bugfixes: * References Resolver: Enforce ``storage`` as data location for mappings. * References Resolver: Properly handle invalid references used together with ``_slot`` and ``_offset``. * References Resolver: Report error instead of assertion fail when FunctionType has an undeclared type as parameter. + * References Resolver: Fix high CPU usage when using large variable names issue. Only suggest similar name if identifiers shorter than 80 characters. * Type Checker: Default data location for type conversions (e.g. from literals) is memory and not storage. * Type Checker: Disallow assignments to mappings within tuple assignments as well. * Type Checker: Disallow packed encoding of arrays of structs. diff --git a/libdevcore/StringUtils.cpp b/libdevcore/StringUtils.cpp index 01bdc675..50bf7cce 100644 --- a/libdevcore/StringUtils.cpp +++ b/libdevcore/StringUtils.cpp @@ -29,13 +29,16 @@ using namespace std; using namespace dev; -bool dev::stringWithinDistance(string const& _str1, string const& _str2, size_t _maxDistance) +bool dev::stringWithinDistance(string const& _str1, string const& _str2, size_t _maxDistance, size_t _lenThreshold) { if (_str1 == _str2) return true; size_t n1 = _str1.size(); size_t n2 = _str2.size(); + if (_lenThreshold > 0 && n1 * n2 > _lenThreshold) + return false; + 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 diff --git a/libdevcore/StringUtils.h b/libdevcore/StringUtils.h index f05a426b..b02b9d12 100644 --- a/libdevcore/StringUtils.h +++ b/libdevcore/StringUtils.h @@ -30,7 +30,8 @@ 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); +// if _lenThreshold > 0 and the product of the strings length is greater than _lenThreshold, the function will return false +bool stringWithinDistance(std::string const& _str1, std::string const& _str2, size_t _maxDistance, size_t _lenThreshold = 0); // 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" diff --git a/libsolidity/analysis/DeclarationContainer.cpp b/libsolidity/analysis/DeclarationContainer.cpp index 347daaf8..5f980788 100644 --- a/libsolidity/analysis/DeclarationContainer.cpp +++ b/libsolidity/analysis/DeclarationContainer.cpp @@ -138,19 +138,22 @@ vector DeclarationContainer::resolveName(ASTString const& _n vector DeclarationContainer::similarNames(ASTString const& _name) const { static size_t const MAXIMUM_EDIT_DISTANCE = 2; + // because the function below has quadratic runtime - it will not magically improve once a better algorithm is discovered ;) + // since 80 is the suggested line length limit, we use 80^2 as length threshold + static size_t const MAXIMUM_LENGTH_THRESHOLD = 80 * 80; vector similar; for (auto const& declaration: m_declarations) { string const& declarationName = declaration.first; - if (stringWithinDistance(_name, declarationName, MAXIMUM_EDIT_DISTANCE)) + if (stringWithinDistance(_name, declarationName, MAXIMUM_EDIT_DISTANCE, MAXIMUM_LENGTH_THRESHOLD)) similar.push_back(declarationName); } for (auto const& declaration: m_invisibleDeclarations) { string const& declarationName = declaration.first; - if (stringWithinDistance(_name, declarationName, MAXIMUM_EDIT_DISTANCE)) + if (stringWithinDistance(_name, declarationName, MAXIMUM_EDIT_DISTANCE, MAXIMUM_LENGTH_THRESHOLD)) similar.push_back(declarationName); } diff --git a/test/libdevcore/StringUtils.cpp b/test/libdevcore/StringUtils.cpp index 94f1b753..76c11b82 100644 --- a/test/libdevcore/StringUtils.cpp +++ b/test/libdevcore/StringUtils.cpp @@ -48,6 +48,7 @@ BOOST_AUTO_TEST_CASE(test_similarity) BOOST_CHECK_EQUAL(stringWithinDistance("abc", "abcdef", 2), false); BOOST_CHECK_EQUAL(stringWithinDistance("abcd", "wxyz", 2), false); BOOST_CHECK_EQUAL(stringWithinDistance("", "", 2), true); + BOOST_CHECK_EQUAL(stringWithinDistance("YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYZ", 2, 6400), false); } BOOST_AUTO_TEST_CASE(test_dldistance) diff --git a/test/libsolidity/syntaxTests/nameAndTypeResolution/573_similar_name_longer_than_80_not_suggested.sol b/test/libsolidity/syntaxTests/nameAndTypeResolution/573_similar_name_longer_than_80_not_suggested.sol new file mode 100644 index 00000000..c6719d8c --- /dev/null +++ b/test/libsolidity/syntaxTests/nameAndTypeResolution/573_similar_name_longer_than_80_not_suggested.sol @@ -0,0 +1,7 @@ +contract test { + function f() public { + int YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY = YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY; + } +} +// ---- +// DeclarationError: (146-236): Undeclared identifier. diff --git a/test/libsolidity/syntaxTests/nameAndTypeResolution/574_similar_name_shorter_than_80_suggested.sol b/test/libsolidity/syntaxTests/nameAndTypeResolution/574_similar_name_shorter_than_80_suggested.sol new file mode 100644 index 00000000..61fb2d82 --- /dev/null +++ b/test/libsolidity/syntaxTests/nameAndTypeResolution/574_similar_name_shorter_than_80_suggested.sol @@ -0,0 +1,7 @@ +contract test { + function f() public { + int YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY = YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY; + } +} +// ---- +// DeclarationError: (137-216): Undeclared identifier. Did you mean "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY"? \ No newline at end of file -- cgit