Merge pull request #3147 from Balajiganapathi/alternative_scope

Suggest alternatives when identifier not found. Closes #3058.

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"(