From 5bdadff0d8a9c32745dd46aa639283718613efdc Mon Sep 17 00:00:00 2001
From: chriseth <chris@ethereum.org>
Date: Thu, 15 Mar 2018 19:07:25 +0100
Subject: Fix detection of recursive structs.

---
 libsolidity/ast/Types.cpp | 5 +++++
 1 file changed, 5 insertions(+)

(limited to 'libsolidity')

diff --git a/libsolidity/ast/Types.cpp b/libsolidity/ast/Types.cpp
index 42fd1c3d..42f6b5ca 100644
--- a/libsolidity/ast/Types.cpp
+++ b/libsolidity/ast/Types.cpp
@@ -1972,9 +1972,12 @@ 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
 		{
 			StructDefinition const* str = &t->structDefinition();
+			if (structsProcessed.count(str))
+				return false;
 			if (structsSeen.count(str))
 				return true;
 			structsSeen.insert(str);
@@ -1987,6 +1990,8 @@ bool StructType::recursive() const
 					if (check(innerStruct))
 						return true;
 			}
+			structsSeen.erase(str);
+			structsProcessed.insert(str);
 			return false;
 		};
 		m_recursive = check(this);
-- 
cgit v1.2.3


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/analysis/PostTypeChecker.cpp | 36 +++++++++++++++++++-------------
 libsolidity/analysis/PostTypeChecker.h   |  5 +----
 libsolidity/ast/Types.cpp                | 22 ++++++-------------
 3 files changed, 28 insertions(+), 35 deletions(-)

(limited to 'libsolidity')

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 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 v1.2.3