From eb5b18e8145d7d3971c450ba220f322e5f66d45c Mon Sep 17 00:00:00 2001
From: chriseth <chris@ethereum.org>
Date: Thu, 15 Mar 2018 19:53:29 +0100
Subject: Generalize cycle detection.

---
 libsolidity/ast/Types.cpp | 22 ++++++----------------
 1 file changed, 6 insertions(+), 16 deletions(-)

(limited to 'libsolidity/ast')

diff --git a/libsolidity/ast/Types.cpp b/libsolidity/ast/Types.cpp
index 42f6b5ca..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,30 +1972,19 @@ bool StructType::recursive() const
 {
 	if (!m_recursive.is_initialized())
 	{
-		set<StructDefinition const*> structsSeen;
-		set<StructDefinition const*> structsProcessed;
-		function<bool(StructType const*)> check = [&](StructType const* t) -> bool
+		auto visitor = [&](StructDefinition const& _struct, CycleDetector<StructDefinition>& _cycleDetector)
 		{
-			StructDefinition const* str = &t->structDefinition();
-			if (structsProcessed.count(str))
-				return false;
-			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;
 			}
-			structsSeen.erase(str);
-			structsProcessed.insert(str);
-			return false;
 		};
-		m_recursive = check(this);
+		m_recursive = (CycleDetector<StructDefinition>(visitor).run(structDefinition()) != nullptr);
 	}
 	return *m_recursive;
 }
-- 
cgit