Merge pull request #3745 from ethereum/fixRecursion

Fix invalid recursion errors for structs

19 files changed, 220 insertions, 155 deletions

diff --git a/Changelog.md b/Changelog.md
index e208437e..7e653ebf 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -22,6 +22,7 @@ Bugfixes:
  * Commandline interface: Support ``--evm-version constantinople`` properly.
  * DocString Parser: Fix error message for empty descriptions.
  * Standard JSON: Support ``constantinople`` as ``evmVersion`` properly.
+ * Type Checker: Fix detection of recursive structs.
  * Type System: Improve error message when attempting to shift by a fractional amount.
  * Type System: Make external library functions accessible.
  * Type System: Prevent encoding of weird types.
diff --git a/libdevcore/Algorithms.h b/libdevcore/Algorithms.h
new file mode 100644
index 00000000..b2540668
--- /dev/null
+++ b/libdevcore/Algorithms.h
@@ -0,0 +1,76 @@
+/*
+	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/>.
+*/
+#pragma once
+
+
+#include <functional>
+#include <set>
+
+namespace dev
+{
+
+/**
+ * Detector for cycles in directed graphs. It returns the first
+ * vertex on the path towards a cycle or a nullptr if there is
+ * no reachable cycle starting from a given vertex.
+ */
+template <typename V>
+class CycleDetector
+{
+public:
+	/// Initializes the cycle detector
+	/// @param _visit function that is given the current vertex
+	///               and is supposed to call @a run on all
+	///               adjacent vertices.
+	explicit CycleDetector(std::function<void(V const&, CycleDetector&)> _visit):
+		m_visit(std::move(_visit))
+	{  }
+
+	/// Recursively perform cycle detection starting
+	/// (or continuing) with @param _vertex
+	/// @returns the first vertex on the path towards a cycle from @a _vertex
+	/// or nullptr if no cycle is reachable from @a _vertex.
+	V const* run(V const& _vertex)
+	{
+		if (m_firstCycleVertex)
+			return m_firstCycleVertex;
+		if (m_processed.count(&_vertex))
+			return nullptr;
+		else if (m_processing.count(&_vertex))
+			return m_firstCycleVertex = &_vertex;
+		m_processing.insert(&_vertex);
+
+		m_depth++;
+		m_visit(_vertex, *this);
+		m_depth--;
+		if (m_firstCycleVertex && m_depth == 1)
+			m_firstCycleVertex = &_vertex;
+
+		m_processing.erase(&_vertex);
+		m_processed.insert(&_vertex);
+		return m_firstCycleVertex;
+	}
+
+private:
+	std::function<void(V const&, CycleDetector&)> m_visit;
+	std::set<V const*> m_processing;
+	std::set<V const*> m_processed;
+	size_t m_depth = 0;
+	V const* m_firstCycleVertex = nullptr;
+};
+
+}
diff --git a/libsolidity/analysis/PostTypeChecker.cpp b/libsolidity/analysis/PostTypeChecker.cpp
index fbc72e52..19d0b708 100644
--- a/libsolidity/analysis/PostTypeChecker.cpp
+++ b/libsolidity/analysis/PostTypeChecker.cpp
@@ -21,6 +21,8 @@
 #include <libsolidity/interface/ErrorReporter.h>
 #include <libsolidity/interface/Version.h>
 
+#include <libdevcore/Algorithms.h>
+
 #include <boost/range/adaptor/map.hpp>
 
 #include <memory>
@@ -47,7 +49,7 @@ void PostTypeChecker::endVisit(ContractDefinition const&)
 {
 	solAssert(!m_currentConstVariable, "");
 	for (auto declaration: m_constVariables)
-		if (auto identifier = findCycle(declaration))
+		if (auto identifier = findCycle(*declaration))
 			m_errorReporter.typeError(
 				declaration->location(),
 				"The value of the constant " + declaration->name() +
@@ -87,20 +89,24 @@ bool PostTypeChecker::visit(Identifier const& _identifier)
 	return true;
 }
 
-VariableDeclaration const* PostTypeChecker::findCycle(
-	VariableDeclaration const* _startingFrom,
-	set<VariableDeclaration const*> const& _seen
-)
+VariableDeclaration const* PostTypeChecker::findCycle(VariableDeclaration const& _startingFrom)
 {
-	if (_seen.count(_startingFrom))
-		return _startingFrom;
-	else if (m_constVariableDependencies.count(_startingFrom))
+	auto visitor = [&](VariableDeclaration const& _variable, CycleDetector<VariableDeclaration>& _cycleDetector)
 	{
-		set<VariableDeclaration const*> seen(_seen);
-		seen.insert(_startingFrom);
-		for (auto v: m_constVariableDependencies[_startingFrom])
-			if (findCycle(v, seen))
-				return v;
-	}
-	return nullptr;
+		// Iterating through the dependencies needs to be deterministic and thus cannot
+		// depend on the memory layout.
+		// Because of that, we sort by AST node id.
+		vector<VariableDeclaration const*> dependencies(
+			m_constVariableDependencies[&_variable].begin(),
+			m_constVariableDependencies[&_variable].end()
+		);
+		sort(dependencies.begin(), dependencies.end(), [](VariableDeclaration const* _a, VariableDeclaration const* _b) -> bool
+		{
+			return _a->id() < _b->id();
+		});
+		for (auto v: dependencies)
+			if (_cycleDetector.run(*v))
+				return;
+	};
+	return CycleDetector<VariableDeclaration>(visitor).run(_startingFrom);
 }
diff --git a/libsolidity/analysis/PostTypeChecker.h b/libsolidity/analysis/PostTypeChecker.h
index bafc1ae6..4f9dac6e 100644
--- a/libsolidity/analysis/PostTypeChecker.h
+++ b/libsolidity/analysis/PostTypeChecker.h
@@ -55,10 +55,7 @@ private:
 
 	virtual bool visit(Identifier const& _identifier) override;
 
-	VariableDeclaration const* findCycle(
-		VariableDeclaration const* _startingFrom,
-		std::set<VariableDeclaration const*> const& _seen = std::set<VariableDeclaration const*>{}
-	);
+	VariableDeclaration const* findCycle(VariableDeclaration const& _startingFrom);
 
 	ErrorReporter& m_errorReporter;
 
diff --git a/libsolidity/ast/Types.cpp b/libsolidity/ast/Types.cpp
index 42fd1c3d..ac1d3b01 100644
--- a/libsolidity/ast/Types.cpp
+++ b/libsolidity/ast/Types.cpp
@@ -28,6 +28,7 @@
 #include <libdevcore/CommonData.h>
 #include <libdevcore/SHA3.h>
 #include <libdevcore/UTF8.h>
+#include <libdevcore/Algorithms.h>
 
 #include <boost/algorithm/string/join.hpp>
 #include <boost/algorithm/string/replace.hpp>
@@ -1971,25 +1972,19 @@ bool StructType::recursive() const
 {
 	if (!m_recursive.is_initialized())
 	{
-		set<StructDefinition const*> structsSeen;
-		function<bool(StructType const*)> check = [&](StructType const* t) -> bool
+		auto visitor = [&](StructDefinition const& _struct, CycleDetector<StructDefinition>& _cycleDetector)
 		{
-			StructDefinition const* str = &t->structDefinition();
-			if (structsSeen.count(str))
-				return true;
-			structsSeen.insert(str);
-			for (ASTPointer<VariableDeclaration> const& variable: str->members())
+			for (ASTPointer<VariableDeclaration> const& variable: _struct.members())
 			{
 				Type const* memberType = variable->annotation().type.get();
 				while (dynamic_cast<ArrayType const*>(memberType))
 					memberType = dynamic_cast<ArrayType const*>(memberType)->baseType().get();
 				if (StructType const* innerStruct = dynamic_cast<StructType const*>(memberType))
-					if (check(innerStruct))
-						return true;
+					if (_cycleDetector.run(innerStruct->structDefinition()))
+						return;
 			}
-			return false;
 		};
-		m_recursive = check(this);
+		m_recursive = (CycleDetector<StructDefinition>(visitor).run(structDefinition()) != nullptr);
 	}
 	return *m_recursive;
 }
diff --git a/test/libsolidity/SolidityNameAndTypeResolution.cpp b/test/libsolidity/SolidityNameAndTypeResolution.cpp
index b6596327..fcee0df3 100644
--- a/test/libsolidity/SolidityNameAndTypeResolution.cpp
+++ b/test/libsolidity/SolidityNameAndTypeResolution.cpp
@@ -92,61 +92,6 @@ BOOST_AUTO_TEST_CASE(reference_to_later_declaration)
 	CHECK_SUCCESS(text);
 }
 
-BOOST_AUTO_TEST_CASE(struct_definition_directly_recursive)
-{
-	char const* text = R"(
-		contract test {
-			struct MyStructName {
-				address addr;
-				MyStructName x;
-			}
-		}
-	)";
-	CHECK_ERROR(text, TypeError, "Recursive struct definition.");
-}
-
-BOOST_AUTO_TEST_CASE(struct_definition_indirectly_recursive)
-{
-	char const* text = R"(
-		contract test {
-			struct MyStructName1 {
-				address addr;
-				uint256 count;
-				MyStructName2 x;
-			}
-			struct MyStructName2 {
-				MyStructName1 x;
-			}
-		}
-	)";
-	CHECK_ERROR(text, TypeError, "Recursive struct definition.");
-}
-
-BOOST_AUTO_TEST_CASE(struct_definition_not_really_recursive)
-{
-	char const* text = R"(
-		contract test {
-			struct s1 { uint a; }
-			struct s2 { s1 x; s1 y; }
-		}
-	)";
-	CHECK_SUCCESS(text);
-}
-
-BOOST_AUTO_TEST_CASE(struct_definition_recursion_via_mapping)
-{
-	char const* text = R"(
-		contract test {
-				struct MyStructName1 {
-					address addr;
-					uint256 count;
-					mapping(uint => MyStructName1) x;
-				}
-			}
- )";
-	CHECK_SUCCESS(text);
-}
-
 BOOST_AUTO_TEST_CASE(type_inference_smoke_test)
 {
 	char const* text = R"(
@@ -6222,44 +6167,6 @@ BOOST_AUTO_TEST_CASE(read_returned_struct)
 	)";
 	CHECK_WARNING(text, "Experimental features");
 }
-
-BOOST_AUTO_TEST_CASE(return_recursive_structs)
-{
-	char const* text = R"(
-		contract C {
-			struct S { uint a; S[] sub; }
-			function f() returns (uint, S) {
-			}
-		}
-	)";
-	CHECK_ERROR(text, TypeError, "Internal or recursive type is not allowed for public or external functions.");
-}
-
-BOOST_AUTO_TEST_CASE(return_recursive_structs2)
-{
-	char const* text = R"(
-		contract C {
-			struct S { uint a; S[2][] sub; }
-			function f() returns (uint, S) {
-			}
-		}
-	)";
-	CHECK_ERROR(text, TypeError, "Internal or recursive type is not allowed for public or external functions.");
-}
-
-BOOST_AUTO_TEST_CASE(return_recursive_structs3)
-{
-	char const* text = R"(
-		contract C {
-			struct S { uint a; S[][][] sub; }
-			struct T { S s; }
-			function f() returns (uint x, T t) {
-			}
-		}
-	)";
-	CHECK_ERROR(text, TypeError, "Internal or recursive type is not allowed for public or external functions.");
-}
-
 BOOST_AUTO_TEST_CASE(address_checksum_type_deduction)
 {
 	char const* text = R"(
@@ -6382,38 +6289,6 @@ BOOST_AUTO_TEST_CASE(address_methods)
 	CHECK_SUCCESS(text);
 }
 
-BOOST_AUTO_TEST_CASE(cyclic_dependency_for_constants)
-{
-	char const* text = R"(
-		contract C {
-			uint constant a = a;
-		}
-	)";
-	CHECK_ERROR(text, TypeError, "cyclic dependency via a");
-	text = R"(
-		contract C {
-			uint constant a = b * c;
-			uint constant b = 7;
-			uint constant c = b + uint(keccak256(d));
-			uint constant d = 2 + a;
-		}
-	)";
-	CHECK_ERROR_ALLOW_MULTI(text, TypeError, (std::vector<std::string>{
-		"a has a cyclic dependency via c",
-		"c has a cyclic dependency via d",
-		"d has a cyclic dependency via a"
-	}));
-	text = R"(
-		contract C {
-			uint constant a = b * c;
-			uint constant b = 7;
-			uint constant c = 4 + uint(keccak256(d));
-			uint constant d = 2 + b;
-		}
-	)";
-	CHECK_SUCCESS(text);
-}
-
 BOOST_AUTO_TEST_CASE(interface)
 {
 	char const* text = R"(
diff --git a/test/libsolidity/syntaxTests/constants/cyclic_dependency_1.sol b/test/libsolidity/syntaxTests/constants/cyclic_dependency_1.sol
new file mode 100644
index 00000000..2b6aa088
--- /dev/null
+++ b/test/libsolidity/syntaxTests/constants/cyclic_dependency_1.sol
@@ -0,0 +1,5 @@
+contract C {
+    uint constant a = a;
+}
+// ----
+// TypeError: The value of the constant a has a cyclic dependency via a.
diff --git a/test/libsolidity/syntaxTests/constants/cyclic_dependency_2.sol b/test/libsolidity/syntaxTests/constants/cyclic_dependency_2.sol
new file mode 100644
index 00000000..461979f8
--- /dev/null
+++ b/test/libsolidity/syntaxTests/constants/cyclic_dependency_2.sol
@@ -0,0 +1,10 @@
+contract C {
+    uint constant a = b * c;
+    uint constant b = 7;
+    uint constant c = b + uint(keccak256(d));
+    uint constant d = 2 + a;
+}
+// ----
+// TypeError: The value of the constant a has a cyclic dependency via c.
+// TypeError: The value of the constant c has a cyclic dependency via d.
+// TypeError: The value of the constant d has a cyclic dependency via a.
diff --git a/test/libsolidity/syntaxTests/constants/cyclic_dependency_3.sol b/test/libsolidity/syntaxTests/constants/cyclic_dependency_3.sol
new file mode 100644
index 00000000..f63be05e
--- /dev/null
+++ b/test/libsolidity/syntaxTests/constants/cyclic_dependency_3.sol
@@ -0,0 +1,11 @@
+contract C {
+    uint constant x = a;
+    uint constant a = b * c;
+    uint constant b = c;
+    uint constant c = b;
+}
+// ----
+// TypeError: The value of the constant x has a cyclic dependency via a.
+// TypeError: The value of the constant a has a cyclic dependency via b.
+// TypeError: The value of the constant b has a cyclic dependency via c.
+// TypeError: The value of the constant c has a cyclic dependency via b.
diff --git a/test/libsolidity/syntaxTests/constants/cyclic_dependency_4.sol b/test/libsolidity/syntaxTests/constants/cyclic_dependency_4.sol
new file mode 100644
index 00000000..f01cb98e
--- /dev/null
+++ b/test/libsolidity/syntaxTests/constants/cyclic_dependency_4.sol
@@ -0,0 +1,6 @@
+contract C {
+    uint constant a = b * c;
+    uint constant b = 7;
+    uint constant c = 4 + uint(keccak256(d));
+    uint constant d = 2 + b;
+}
\ No newline at end of file
diff --git a/test/libsolidity/syntaxTests/structs/recursion/multi_struct_composition.sol b/test/libsolidity/syntaxTests/structs/recursion/multi_struct_composition.sol
new file mode 100644
index 00000000..9a1c22f1
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/multi_struct_composition.sol
@@ -0,0 +1,15 @@
+pragma experimental ABIEncoderV2;
+
+contract C {
+  struct T { U u; V v; }
+
+  struct U { W w; }
+
+  struct V { W w; }
+
+  struct W { uint x; }
+
+  function f(T) public pure { }
+}
+// ----
+// Warning: Experimental features are turned on. Do not use experimental features on live deployments.
diff --git a/test/libsolidity/syntaxTests/structs/recursion/parallel_structs.sol b/test/libsolidity/syntaxTests/structs/recursion/parallel_structs.sol
new file mode 100644
index 00000000..d4ad088d
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/parallel_structs.sol
@@ -0,0 +1,15 @@
+pragma experimental ABIEncoderV2;
+
+contract TestContract
+{
+    struct SubStruct {
+        uint256 id;
+    }
+    struct TestStruct {
+        SubStruct subStruct1;
+        SubStruct subStruct2;
+    }
+    function addTestStruct(TestStruct) public pure {}
+}
+// ----
+// Warning: Experimental features are turned on. Do not use experimental features on live deployments.
diff --git a/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs.sol b/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs.sol
new file mode 100644
index 00000000..c02a8aa4
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs.sol
@@ -0,0 +1,7 @@
+contract C {
+    struct S { uint a; S[] sub; }
+    function f() public pure returns (uint, S) {
+    }
+}
+// ----
+// TypeError: Internal or recursive type is not allowed for public or external functions.
diff --git a/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs2.sol b/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs2.sol
new file mode 100644
index 00000000..e9488cf4
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs2.sol
@@ -0,0 +1,7 @@
+contract C {
+    struct S { uint a; S[2][] sub; }
+    function f() public pure returns (uint, S) {
+    }
+}
+// ----
+// TypeError: Internal or recursive type is not allowed for public or external functions.
diff --git a/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs3.sol b/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs3.sol
new file mode 100644
index 00000000..6728baec
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs3.sol
@@ -0,0 +1,8 @@
+contract C {
+    struct S { uint a; S[][][] sub; }
+    struct T { S s; }
+    function f() public pure returns (uint x, T t) {
+    }
+}
+// ----
+// TypeError: Internal or recursive type is not allowed for public or external functions.
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_directly_recursive.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_directly_recursive.sol
new file mode 100644
index 00000000..cac2e23f
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_directly_recursive.sol
@@ -0,0 +1,8 @@
+contract Test {
+    struct MyStructName {
+        address addr;
+        MyStructName x;
+    }
+}
+// ----
+// TypeError: Recursive struct definition.
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive.sol
new file mode 100644
index 00000000..11fc6307
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive.sol
@@ -0,0 +1,12 @@
+contract Test {
+    struct MyStructName1 {
+        address addr;
+        uint256 count;
+        MyStructName2 x;
+    }
+    struct MyStructName2 {
+        MyStructName1 x;
+    }
+}
+// ----
+// TypeError: Recursive struct definition.
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_not_really_recursive.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_not_really_recursive.sol
new file mode 100644
index 00000000..6ec4ee01
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_not_really_recursive.sol
@@ -0,0 +1,4 @@
+contract Test {
+    struct S1 { uint a; }
+    struct S2 { S1 x; S1 y; }
+}
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_recursion_via_mapping.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_recursion_via_mapping.sol
new file mode 100644
index 00000000..926981b3
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_recursion_via_mapping.sol
@@ -0,0 +1,7 @@
+contract Test {
+    struct MyStructName1 {
+        address addr;
+        uint256 count;
+        mapping(uint => MyStructName1) x;
+    }
+}