Resolve binary dependencies properly.

8 files changed, 106 insertions, 28 deletions

diff --git a/libsolidity/ASTAnnotations.h b/libsolidity/ASTAnnotations.h
index dad7b205..be9b164c 100644
--- a/libsolidity/ASTAnnotations.h
+++ b/libsolidity/ASTAnnotations.h
@@ -25,6 +25,7 @@
 #include <map>
 #include <memory>
 #include <vector>
+#include <set>
 #include <libsolidity/ASTForward.h>
 
 namespace dev
@@ -53,6 +54,9 @@ struct ContractDefinitionAnnotation: TypeDeclarationAnnotation
 	/// List of all (direct and indirect) base contracts in order from derived to
 	/// base, including the contract itself.
 	std::vector<ContractDefinition const*> linearizedBaseContracts;
+	/// List of contracts this contract creates, i.e. which need to be compiled first.
+	/// Also includes all contracts from @a linearizedBaseContracts.
+	std::set<ContractDefinition const*> contractDependencies;
 };
 
 struct VariableDeclarationAnnotation: ASTAnnotation
diff --git a/libsolidity/CompilerStack.cpp b/libsolidity/CompilerStack.cpp
index 7d9ca32c..8c1cd8cf 100644
--- a/libsolidity/CompilerStack.cpp
+++ b/libsolidity/CompilerStack.cpp
@@ -170,22 +170,8 @@ bool CompilerStack::compile(bool _optimize, unsigned _runs)
 	map<ContractDefinition const*, eth::Assembly const*> compiledContracts;
 	for (Source const* source: m_sourceOrder)
 		for (ASTPointer<ASTNode> const& node: source->ast->nodes())
-			if (ContractDefinition* contract = dynamic_cast<ContractDefinition*>(node.get()))
-			{
-				if (!contract->annotation().isFullyImplemented)
-					continue;
-				shared_ptr<Compiler> compiler = make_shared<Compiler>(_optimize, _runs);
-				compiler->compileContract(*contract, compiledContracts);
-				Contract& compiledContract = m_contracts.at(contract->name());
-				compiledContract.compiler = compiler;
-				compiledContract.object = compiler->assembledObject();
-				compiledContract.runtimeObject = compiler->runtimeObject();
-				compiledContracts[compiledContract.contract] = &compiler->assembly();
-
-				Compiler cloneCompiler(_optimize, _runs);
-				cloneCompiler.compileClone(*contract, compiledContracts);
-				compiledContract.cloneObject = cloneCompiler.assembledObject();
-			}
+			if (auto contract = dynamic_cast<ContractDefinition const*>(node.get()))
+				compileContract(_optimize, _runs, *contract, compiledContracts);
 	return true;
 }
 
@@ -375,6 +361,31 @@ void CompilerStack::resolveImports()
 	swap(m_sourceOrder, sourceOrder);
 }
 
+void CompilerStack::compileContract(
+	bool _optimize,
+	unsigned _runs,
+	ContractDefinition const& _contract,
+	map<ContractDefinition const*, eth::Assembly const*>& _compiledContracts
+)
+{
+	if (_compiledContracts.count(&_contract) || !_contract.annotation().isFullyImplemented)
+		return;
+	for (auto const* dependency: _contract.annotation().contractDependencies)
+		compileContract(_optimize, _runs, *dependency, _compiledContracts);
+
+	shared_ptr<Compiler> compiler = make_shared<Compiler>(_optimize, _runs);
+	compiler->compileContract(_contract, _compiledContracts);
+	Contract& compiledContract = m_contracts.at(_contract.name());
+	compiledContract.compiler = compiler;
+	compiledContract.object = compiler->assembledObject();
+	compiledContract.runtimeObject = compiler->runtimeObject();
+	_compiledContracts[compiledContract.contract] = &compiler->assembly();
+
+	Compiler cloneCompiler(_optimize, _runs);
+	cloneCompiler.compileClone(_contract, _compiledContracts);
+	compiledContract.cloneObject = cloneCompiler.assembledObject();
+}
+
 std::string CompilerStack::defaultContractName() const
 {
 	return contract("").contract->name();
diff --git a/libsolidity/CompilerStack.h b/libsolidity/CompilerStack.h
index e541ea47..da26148d 100644
--- a/libsolidity/CompilerStack.h
+++ b/libsolidity/CompilerStack.h
@@ -39,6 +39,7 @@ namespace dev
 
 namespace eth
 {
+class Assembly;
 class AssemblyItem;
 using AssemblyItems = std::vector<AssemblyItem>;
 }
@@ -195,6 +196,13 @@ private:
 	};
 
 	void resolveImports();
+	/// Compile a single contract and put the result in @a _compiledContracts.
+	void compileContract(
+		bool _optimize,
+		unsigned _runs,
+		ContractDefinition const& _contract,
+		std::map<ContractDefinition const*, eth::Assembly const*>& _compiledContracts
+	);
 
 	Contract const& contract(std::string const& _contractName = "") const;
 	Source const& source(std::string const& _sourceName = "") const;
diff --git a/libsolidity/NameAndTypeResolver.cpp b/libsolidity/NameAndTypeResolver.cpp
index 4747542d..0ce20f3c 100644
--- a/libsolidity/NameAndTypeResolver.cpp
+++ b/libsolidity/NameAndTypeResolver.cpp
@@ -216,6 +216,7 @@ void NameAndTypeResolver::linearizeBaseContracts(ContractDefinition& _contract)
 	if (result.empty())
 		BOOST_THROW_EXCEPTION(_contract.createTypeError("Linearization of inheritance graph impossible"));
 	_contract.annotation().linearizedBaseContracts = result;
+	_contract.annotation().contractDependencies.insert(result.begin() + 1, result.end());
 }
 
 template <class _T>
diff --git a/libsolidity/TypeChecker.cpp b/libsolidity/TypeChecker.cpp
index 2afa5649..4b4fc7f1 100644
--- a/libsolidity/TypeChecker.cpp
+++ b/libsolidity/TypeChecker.cpp
@@ -908,12 +908,15 @@ void TypeChecker::endVisit(NewExpression const& _newExpression)
 		typeError(_newExpression, "Trying to create an instance of an abstract contract.");
 
 	auto scopeContract = _newExpression.contractName().annotation().contractScope;
-	auto const& bases = contract->annotation().linearizedBaseContracts;
-	solAssert(!bases.empty(), "Linearized base contracts not yet available.");
-	if (find(bases.begin(), bases.end(), scopeContract) != bases.end())
+	scopeContract->annotation().contractDependencies.insert(contract);
+	solAssert(
+		!contract->annotation().linearizedBaseContracts.empty(),
+		"Linearized base contracts not yet available."
+	);
+	if (contractDependenciesAreCyclic(*scopeContract))
 		typeError(
 			_newExpression,
-			"Circular reference for contract creation: cannot create instance of derived or same contract."
+			"Circular reference for contract creation (cannot create instance of derived or same contract)."
 		);
 
 	auto contractType = make_shared<ContractType>(*contract);
@@ -1118,6 +1121,22 @@ void TypeChecker::endVisit(Literal const& _literal)
 		fatalTypeError(_literal, "Invalid literal value.");
 }
 
+bool TypeChecker::contractDependenciesAreCyclic(
+	ContractDefinition const& _contract,
+	std::set<ContractDefinition const*> const& _seenContracts
+) const
+{
+	// Naive depth-first search that remembers nodes already seen.
+	if (_seenContracts.count(&_contract))
+		return true;
+	set<ContractDefinition const*> seen(_seenContracts);
+	seen.insert(&_contract);
+	for (auto const* c: _contract.annotation().contractDependencies)
+		if (contractDependenciesAreCyclic(*c, seen))
+			return true;
+	return false;
+}
+
 Declaration const& TypeChecker::dereference(Identifier const& _identifier)
 {
 	solAssert(!!_identifier.annotation().referencedDeclaration, "Declaration not stored.");
diff --git a/libsolidity/TypeChecker.h b/libsolidity/TypeChecker.h
index 3f740b7e..97262ed0 100644
--- a/libsolidity/TypeChecker.h
+++ b/libsolidity/TypeChecker.h
@@ -99,6 +99,11 @@ private:
 	virtual void endVisit(ElementaryTypeNameExpression const& _expr) override;
 	virtual void endVisit(Literal const& _literal) override;
 
+	bool contractDependenciesAreCyclic(
+		ContractDefinition const& _contract,
+		std::set<ContractDefinition const*> const& _seenContracts = std::set<ContractDefinition const*>()
+	) const;
+
 	/// @returns the referenced declaration and throws on error.
 	Declaration const& dereference(Identifier const& _identifier);
 
diff --git a/test/libsolidity/SolidityEndToEndTest.cpp b/test/libsolidity/SolidityEndToEndTest.cpp
index c96ae14d..3126c1cc 100644
--- a/test/libsolidity/SolidityEndToEndTest.cpp
+++ b/test/libsolidity/SolidityEndToEndTest.cpp
@@ -5555,16 +5555,16 @@ BOOST_AUTO_TEST_CASE(calldata_offset)
 	// This tests a specific bug that was caused by not using the correct memory offset in the
 	// calldata unpacker.
 	char const* sourceCode = R"(
-			contract CB
+		contract CB
+		{
+			address[] _arr;
+			string public last = "nd";
+			function CB(address[] guardians)
 			{
-				address[] _arr;
-				string public last = "nd";
-				function CB(address[] guardians)
-				{
-					_arr = guardians;
-				}
+				_arr = guardians;
 			}
-			)";
+		}
+	)";
 	compileAndRun(sourceCode, 0, "CB", encodeArgs(u256(0x20)));
 	BOOST_CHECK(callContractFunction("last()", encodeArgs()) == encodeDyn(string("nd")));
 }
@@ -5580,6 +5580,16 @@ BOOST_AUTO_TEST_CASE(version_stamp_for_libraries)
 	BOOST_CHECK_EQUAL(runtimeCode[7], int(eth::Instruction::POP));
 }
 
+BOOST_AUTO_TEST_CASE(contract_binary_dependencies)
+{
+	char const* sourceCode = R"(
+		contract A { function f() { new B(); } }
+		contract B { function f() { } }
+		contract C { function f() { new B(); } }
+	)";
+	compileAndRun(sourceCode);
+}
+
 BOOST_AUTO_TEST_CASE(reject_ether_sent_to_library)
 {
 	char const* sourceCode = R"(
diff --git a/test/libsolidity/SolidityNameAndTypeResolution.cpp b/test/libsolidity/SolidityNameAndTypeResolution.cpp
index 33e76ec9..99fdf6d9 100644
--- a/test/libsolidity/SolidityNameAndTypeResolution.cpp
+++ b/test/libsolidity/SolidityNameAndTypeResolution.cpp
@@ -2366,6 +2366,26 @@ BOOST_AUTO_TEST_CASE(non_initialized_references)
 	SOLIDITY_CHECK_ERROR_TYPE(parseAndAnalyseReturnError(text, true), Warning);
 }
 
+BOOST_AUTO_TEST_CASE(cyclic_binary_dependency)
+{
+	char const* text = R"(
+		contract A { function f() { new B(); } }
+		contract B { function f() { new C(); } }
+		contract C { function f() { new A(); } }
+	)";
+	SOLIDITY_CHECK_ERROR_TYPE(parseAndAnalyseReturnError(text), TypeError);
+}
+
+BOOST_AUTO_TEST_CASE(cyclic_binary_dependency_via_inheritance)
+{
+	char const* text = R"(
+		contract A is B { }
+		contract B { function f() { new C(); } }
+		contract C { function f() { new A(); } }
+	)";
+	SOLIDITY_CHECK_ERROR_TYPE(parseAndAnalyseReturnError(text), TypeError);
+}
+
 BOOST_AUTO_TEST_SUITE_END()
 
 }