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. --- 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 ++- 5 files changed, 95 insertions(+), 2 deletions(-) (limited to 'libsolidity/analysis') 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 -- cgit