Suggest alternatives when identifier not found.

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<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 +115,64 @@ 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
+{
+	vector<ASTString> 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<ASTString> 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<vector<size_t>> dp(n1 + 1, vector<size_t>(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<ASTString> similarNames(ASTString const& _name) const;
+
+
 private:
 	ASTNode const* m_enclosingNode;
 	DeclarationContainer const* m_enclosingContainer;
 	std::map<ASTString, std::vector<Declaration const*>> m_declarations;
 	std::map<ASTString, std::vector<Declaration const*>> 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<list<_T const*>>& _toMer
 	return result;
 }
 
+string NameAndTypeResolver::similarNameSuggestions(ASTString const& _name) const
+{
+	vector<ASTString> 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<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..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"(