Merge pull request #4501 from ethereum/recursiveStructsWithFixedArrays

Consider fixed-size arrays when checking for recursive structs.

14 files changed, 156 insertions, 13 deletions

diff --git a/Changelog.md b/Changelog.md
index 2127d9c5..b27254a8 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -65,6 +65,7 @@ Bugfixes:
  * Tests: Fix chain parameters to make ipc tests work with newer versions of cpp-ethereum.
  * Code Generator: Fix allocation of byte arrays (zeroed out too much memory).
  * Fix NatSpec json output for `@notice` and `@dev` tags on contract definitions.
+ * Type Checker: Consider fixed size arrays when checking for recursive structs.
  * Type System: Allow arbitrary exponents for literals with a mantissa of zero.
 
 ### 0.4.24 (2018-05-16)
diff --git a/libsolidity/analysis/TypeChecker.cpp b/libsolidity/analysis/TypeChecker.cpp
index e2e4d9c3..cc373e03 100644
--- a/libsolidity/analysis/TypeChecker.cpp
+++ b/libsolidity/analysis/TypeChecker.cpp
@@ -30,6 +30,7 @@
 #include <libsolidity/inlineasm/AsmAnalysisInfo.h>
 #include <libsolidity/inlineasm/AsmData.h>
 #include <libsolidity/interface/ErrorReporter.h>
+#include <libdevcore/Algorithms.h>
 
 using namespace std;
 using namespace dev;
@@ -593,22 +594,24 @@ bool TypeChecker::visit(StructDefinition const& _struct)
 			m_errorReporter.typeError(member->location(), "Type cannot be used in struct.");
 
 	// Check recursion, fatal error if detected.
-	using StructPointer = StructDefinition const*;
-	using StructPointersSet = set<StructPointer>;
-	function<void(StructPointer,StructPointersSet const&)> check = [&](StructPointer _struct, StructPointersSet const& _parents)
-	{
-		if (_parents.count(_struct))
-			m_errorReporter.fatalTypeError(_struct->location(), "Recursive struct definition.");
-		StructPointersSet parents = _parents;
-		parents.insert(_struct);
-		for (ASTPointer<VariableDeclaration> const& member: _struct->members())
-			if (type(*member)->category() == Type::Category::Struct)
+	auto visitor = [&](StructDefinition const& _struct, CycleDetector<StructDefinition>& _cycleDetector)
+	{
+		for (ASTPointer<VariableDeclaration> const& member: _struct.members())
+		{
+			Type const* memberType = type(*member).get();
+			while (auto arrayType = dynamic_cast<ArrayType const*>(memberType))
 			{
-				auto const& typeName = dynamic_cast<UserDefinedTypeName const&>(*member->typeName());
-				check(&dynamic_cast<StructDefinition const&>(*typeName.annotation().referencedDeclaration), parents);
+				if (arrayType->isDynamicallySized())
+					break;
+				memberType = arrayType->baseType().get();
 			}
+			if (auto structType = dynamic_cast<StructType const*>(memberType))
+				if (_cycleDetector.run(structType->structDefinition()))
+					return;
+		}
 	};
-	check(&_struct, StructPointersSet{});
+	if (CycleDetector<StructDefinition>(visitor).run(_struct) != nullptr)
+		m_errorReporter.fatalTypeError(_struct.location(), "Recursive struct definition.");
 
 	ASTNode::listAccept(_struct.members(), *this);
 
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_directly_recursive_dynamic_array.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_directly_recursive_dynamic_array.sol
new file mode 100644
index 00000000..d847f17c
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_directly_recursive_dynamic_array.sol
@@ -0,0 +1,7 @@
+contract Test {
+    struct MyStructName {
+        address addr;
+        MyStructName[] x;
+    }
+}
+// ----
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_directly_recursive_fixed_array.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_directly_recursive_fixed_array.sol
new file mode 100644
index 00000000..126dda4f
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_directly_recursive_fixed_array.sol
@@ -0,0 +1,8 @@
+contract Test {
+    struct MyStructName {
+        address addr;
+        MyStructName[1] x;
+    }
+}
+// ----
+// TypeError: (20-96): Recursive struct definition.
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_complex.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_complex.sol
new file mode 100644
index 00000000..6d35a5d3
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_complex.sol
@@ -0,0 +1,18 @@
+contract Test {
+    struct MyStructName1 {
+        address addr;
+        uint256 count;
+        MyStructName4[1] x;
+    }
+    struct MyStructName2 {
+        MyStructName1 x;
+    }
+    struct MyStructName3 {
+        MyStructName2[1] x;
+    }
+    struct MyStructName4 {
+        MyStructName3 x;
+    }
+}
+// ----
+// TypeError: (20-121): Recursive struct definition.
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_dynamic_array1.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_dynamic_array1.sol
new file mode 100644
index 00000000..10d7de2c
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_dynamic_array1.sol
@@ -0,0 +1,11 @@
+contract Test {
+    struct MyStructName1 {
+        address addr;
+        uint256 count;
+        MyStructName2[] x;
+    }
+    struct MyStructName2 {
+        MyStructName1 x;
+    }
+}
+// ----
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_dynamic_array2.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_dynamic_array2.sol
new file mode 100644
index 00000000..f20510ca
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_dynamic_array2.sol
@@ -0,0 +1,11 @@
+contract Test {
+    struct MyStructName1 {
+        address addr;
+        uint256 count;
+        MyStructName2 x;
+    }
+    struct MyStructName2 {
+        MyStructName1[] x;
+    }
+}
+// ----
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_dynamic_array3.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_dynamic_array3.sol
new file mode 100644
index 00000000..69747e71
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_dynamic_array3.sol
@@ -0,0 +1,11 @@
+contract Test {
+    struct MyStructName1 {
+        address addr;
+        uint256 count;
+        MyStructName2[] x;
+    }
+    struct MyStructName2 {
+        MyStructName1[] x;
+    }
+}
+// ----
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_dynamic_multi_array.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_dynamic_multi_array.sol
new file mode 100644
index 00000000..b3507828
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_dynamic_multi_array.sol
@@ -0,0 +1,21 @@
+contract Test {
+    struct S1 {
+        S2[1][] x;
+    }
+    struct S2 {
+        S1 x;
+    }
+    struct T1 {
+        T2[][1] x;
+    }
+    struct T2 {
+        T1 x;
+    }
+    struct R1 {
+        R2[][] x;
+    }
+    struct R2 {
+        R1 x;
+    }
+}
+// ----
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_fixed_array1.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_fixed_array1.sol
new file mode 100644
index 00000000..2c0b90ec
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_fixed_array1.sol
@@ -0,0 +1,12 @@
+contract Test {
+    struct MyStructName1 {
+        address addr;
+        uint256 count;
+        MyStructName2[1] x;
+    }
+    struct MyStructName2 {
+        MyStructName1 x;
+    }
+}
+// ----
+// TypeError: (20-121): Recursive struct definition.
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_fixed_array2.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_fixed_array2.sol
new file mode 100644
index 00000000..3178e569
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_fixed_array2.sol
@@ -0,0 +1,12 @@
+contract Test {
+    struct MyStructName1 {
+        address addr;
+        uint256 count;
+        MyStructName2 x;
+    }
+    struct MyStructName2 {
+        MyStructName1[1] x;
+    }
+}
+// ----
+// TypeError: (20-118): Recursive struct definition.
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_fixed_array3.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_fixed_array3.sol
new file mode 100644
index 00000000..e34cf9bc
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_fixed_array3.sol
@@ -0,0 +1,12 @@
+contract Test {
+    struct MyStructName1 {
+        address addr;
+        uint256 count;
+        MyStructName2[1] x;
+    }
+    struct MyStructName2 {
+        MyStructName1[1] x;
+    }
+}
+// ----
+// TypeError: (20-121): Recursive struct definition.
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_fixed_multi_array.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_fixed_multi_array.sol
new file mode 100644
index 00000000..ed659b6e
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive_fixed_multi_array.sol
@@ -0,0 +1,12 @@
+contract Test {
+    struct MyStructName1 {
+        address addr;
+        uint256 count;
+        MyStructName2[1][1] x;
+    }
+    struct MyStructName2 {
+        MyStructName1 x;
+    }
+}
+// ----
+// TypeError: (20-124): Recursive struct definition.
diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_not_really_recursive_array.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_not_really_recursive_array.sol
new file mode 100644
index 00000000..b2053b8a
--- /dev/null
+++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_not_really_recursive_array.sol
@@ -0,0 +1,4 @@
+contract Test {
+    struct S1 { uint a; }
+    struct S2 { S1[1] x; S1[1] y; }
+}