Guard CycleDetector against recursion exhaustion.

fixes #3935.

5 files changed, 15 insertions, 6 deletions

diff --git a/Changelog.md b/Changelog.md
index bcd55955..6bab91ee 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -46,6 +46,7 @@ Breaking Changes:
  * Type Checker: Disallow specifying base constructor arguments multiple times in the same inheritance hierarchy. This was already the case in the experimental 0.5.0 mode.
  * Type Checker: Disallow calling constructor with wrong argument count. This was already the case in the experimental 0.5.0 mode.
  * Type Checker: Disallow uninitialized storage variables. This was already the case in the experimental 0.5.0 mode.
+ * Type Checker: Detecting cyclic dependencies in variables and structs is limited in recursion to 256.
  * Type Checker: Only accept a single ``bytes`` type for ``.call()`` (and family), ``keccak256()``, ``sha256()`` and ``ripemd160()``.
  * Type Checker: Fallback function must be external. This was already the case in the experimental 0.5.0 mode.
  * Type Checker: Interface functions must be declared external. This was already the case in the experimental 0.5.0 mode.
diff --git a/libdevcore/Algorithms.h b/libdevcore/Algorithms.h
index b2540668..7fe2472d 100644
--- a/libdevcore/Algorithms.h
+++ b/libdevcore/Algorithms.h
@@ -32,11 +32,13 @@ template <typename V>
 class CycleDetector
 {
 public:
+	using Visitor = std::function<void(V const&, CycleDetector&, size_t)>;
+
 	/// 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):
+	explicit CycleDetector(Visitor _visit):
 		m_visit(std::move(_visit))
 	{  }
 
@@ -55,7 +57,7 @@ public:
 		m_processing.insert(&_vertex);
 
 		m_depth++;
-		m_visit(_vertex, *this);
+		m_visit(_vertex, *this, m_depth);
 		m_depth--;
 		if (m_firstCycleVertex && m_depth == 1)
 			m_firstCycleVertex = &_vertex;
@@ -66,7 +68,7 @@ public:
 	}
 
 private:
-	std::function<void(V const&, CycleDetector&)> m_visit;
+	Visitor m_visit;
 	std::set<V const*> m_processing;
 	std::set<V const*> m_processed;
 	size_t m_depth = 0;
diff --git a/libsolidity/analysis/PostTypeChecker.cpp b/libsolidity/analysis/PostTypeChecker.cpp
index 19d0b708..240d7973 100644
--- a/libsolidity/analysis/PostTypeChecker.cpp
+++ b/libsolidity/analysis/PostTypeChecker.cpp
@@ -91,8 +91,11 @@ bool PostTypeChecker::visit(Identifier const& _identifier)
 
 VariableDeclaration const* PostTypeChecker::findCycle(VariableDeclaration const& _startingFrom)
 {
-	auto visitor = [&](VariableDeclaration const& _variable, CycleDetector<VariableDeclaration>& _cycleDetector)
+	auto visitor = [&](VariableDeclaration const& _variable, CycleDetector<VariableDeclaration>& _cycleDetector, size_t _depth)
 	{
+		if (_depth >= 256)
+			m_errorReporter.fatalDeclarationError(_variable.location(), "Variable definition exhausting cyclic dependency validator.");
+
 		// 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.
diff --git a/libsolidity/analysis/TypeChecker.cpp b/libsolidity/analysis/TypeChecker.cpp
index d2fb9281..fdc7b434 100644
--- a/libsolidity/analysis/TypeChecker.cpp
+++ b/libsolidity/analysis/TypeChecker.cpp
@@ -595,8 +595,11 @@ bool TypeChecker::visit(StructDefinition const& _struct)
 			m_errorReporter.typeError(member->location(), "Type cannot be used in struct.");
 
 	// Check recursion, fatal error if detected.
-	auto visitor = [&](StructDefinition const& _struct, CycleDetector<StructDefinition>& _cycleDetector)
+	auto visitor = [&](StructDefinition const& _struct, CycleDetector<StructDefinition>& _cycleDetector, size_t _depth)
 	{
+		if (_depth >= 256)
+			m_errorReporter.fatalDeclarationError(_struct.location(), "Struct definition exhausting cyclic dependency validator.");
+
 		for (ASTPointer<VariableDeclaration> const& member: _struct.members())
 		{
 			Type const* memberType = type(*member).get();
diff --git a/libsolidity/ast/Types.cpp b/libsolidity/ast/Types.cpp
index 7b079f45..c85e0522 100644
--- a/libsolidity/ast/Types.cpp
+++ b/libsolidity/ast/Types.cpp
@@ -2119,7 +2119,7 @@ bool StructType::recursive() const
 {
 	if (!m_recursive.is_initialized())
 	{
-		auto visitor = [&](StructDefinition const& _struct, CycleDetector<StructDefinition>& _cycleDetector)
+		auto visitor = [&](StructDefinition const& _struct, CycleDetector<StructDefinition>& _cycleDetector, size_t /*_depth*/)
 		{
 			for (ASTPointer<VariableDeclaration> const& variable: _struct.members())
 			{