Import inherited members into the contract's scope.

4 files changed, 121 insertions, 3 deletions

diff --git a/AST.h b/AST.h
index e4761536..b3fd840a 100755
--- a/AST.h
+++ b/AST.h
@@ -173,6 +173,7 @@ public:
 	virtual void accept(ASTVisitor& _visitor) override;
 	virtual void accept(ASTConstVisitor& _visitor) const override;
 
+	std::vector<ASTPointer<Identifier>> const& getBaseContracts() const { return m_baseContracts; }
 	std::vector<ASTPointer<StructDefinition>> const& getDefinedStructs() const { return m_definedStructs; }
 	std::vector<ASTPointer<VariableDeclaration>> const& getStateVariables() const { return m_stateVariables; }
 	std::vector<ASTPointer<FunctionDefinition>> const& getDefinedFunctions() const { return m_definedFunctions; }
@@ -189,6 +190,11 @@ public:
 	/// as intended for use by the ABI.
 	std::map<FixedHash<4>, FunctionDefinition const*> getInterfaceFunctions() const;
 
+	/// List of all (direct and indirect) base contracts in order from derived to base, including
+	/// the contract itself. Available after name resolution
+	std::vector<ContractDefinition const*> const& getLinearizedBaseContracts() const { return m_linearizedBaseContracts; }
+	void setLinearizedBaseContracts(std::vector<ContractDefinition const*> const& _bases) { m_linearizedBaseContracts = _bases; }
+
 	/// Returns the constructor or nullptr if no constructor was specified
 	FunctionDefinition const* getConstructor() const;
 
@@ -200,6 +206,8 @@ private:
 	std::vector<ASTPointer<VariableDeclaration>> m_stateVariables;
 	std::vector<ASTPointer<FunctionDefinition>> m_definedFunctions;
 	ASTPointer<ASTString> m_documentation;
+
+	std::vector<ContractDefinition const*> m_linearizedBaseContracts;
 };
 
 class StructDefinition: public Declaration
diff --git a/DeclarationContainer.h b/DeclarationContainer.h
index c0a0b42c..e4b79325 100644
--- a/DeclarationContainer.h
+++ b/DeclarationContainer.h
@@ -42,11 +42,12 @@ public:
 	explicit DeclarationContainer(Declaration const* _enclosingDeclaration = nullptr,
 								  DeclarationContainer const* _enclosingContainer = nullptr):
 		m_enclosingDeclaration(_enclosingDeclaration), m_enclosingContainer(_enclosingContainer) {}
-	/// Registers the declaration in the scope unless its name is already declared. Returns true iff
-	/// it was not yet declared.
+	/// Registers the declaration in the scope unless its name is already declared.
+	/// @returns true iff it was not yet declared.
 	bool registerDeclaration(Declaration const& _declaration, bool _update = false);
 	Declaration const* resolveName(ASTString const& _name, bool _recursive = false) const;
 	Declaration const* getEnclosingDeclaration() const { return m_enclosingDeclaration; }
+	std::map<ASTString, Declaration const*> const& getDeclarations() const { return m_declarations; }
 
 private:
 	Declaration const* m_enclosingDeclaration;
diff --git a/NameAndTypeResolver.cpp b/NameAndTypeResolver.cpp
index 3774537d..2a73f21b 100644
--- a/NameAndTypeResolver.cpp
+++ b/NameAndTypeResolver.cpp
@@ -46,7 +46,17 @@ void NameAndTypeResolver::registerDeclarations(SourceUnit& _sourceUnit)
 
 void NameAndTypeResolver::resolveNamesAndTypes(ContractDefinition& _contract)
 {
+	m_currentScope = &m_scopes[nullptr];
+
+	for (ASTPointer<Identifier> const& baseContract: _contract.getBaseContracts())
+		ReferencesResolver resolver(*baseContract, *this, nullptr);
+
 	m_currentScope = &m_scopes[&_contract];
+
+	linearizeBaseContracts(_contract);
+	for (ContractDefinition const* base: _contract.getLinearizedBaseContracts())
+		importInheritedScope(*base);
+
 	for (ASTPointer<StructDefinition> const& structDef: _contract.getDefinedStructs())
 		ReferencesResolver resolver(*structDef, *this, nullptr);
 	for (ASTPointer<VariableDeclaration> const& variable: _contract.getStateVariables())
@@ -57,7 +67,6 @@ void NameAndTypeResolver::resolveNamesAndTypes(ContractDefinition& _contract)
 		ReferencesResolver referencesResolver(*function, *this,
 											  function->getReturnParameterList().get());
 	}
-	m_currentScope = &m_scopes[nullptr];
 }
 
 void NameAndTypeResolver::checkTypeRequirements(ContractDefinition& _contract)
@@ -86,6 +95,94 @@ Declaration const* NameAndTypeResolver::getNameFromCurrentScope(ASTString const&
 	return m_currentScope->resolveName(_name, _recursive);
 }
 
+void NameAndTypeResolver::importInheritedScope(ContractDefinition const& _base)
+{
+	auto iterator = m_scopes.find(&_base);
+	solAssert(iterator != end(m_scopes), "");
+	for (auto const& nameAndDeclaration: iterator->second.getDeclarations())
+	{
+		Declaration const* declaration = nameAndDeclaration.second;
+		if (declaration->getScope() == &_base)
+			m_currentScope->registerDeclaration(*declaration);
+	}
+}
+
+void NameAndTypeResolver::linearizeBaseContracts(ContractDefinition& _contract) const
+{
+	// order in the lists is from derived to base
+	// list of lists to linearize, the last element is the list of direct bases
+	list<list<ContractDefinition const*>> input(1, {&_contract});
+	for (ASTPointer<Identifier> const& baseIdentifier: _contract.getBaseContracts())
+	{
+		ContractDefinition const* base = dynamic_cast<ContractDefinition const*>(
+														baseIdentifier->getReferencedDeclaration());
+		if (!base)
+			BOOST_THROW_EXCEPTION(baseIdentifier->createTypeError("Contract expected."));
+		// "push_back" has the effect that bases mentioned earlier can overwrite members of bases
+		// mentioned later
+		input.back().push_back(base);
+		vector<ContractDefinition const*> const& basesBases = base->getLinearizedBaseContracts();
+		if (basesBases.empty())
+			BOOST_THROW_EXCEPTION(baseIdentifier->createTypeError("Definition of base has to precede definition of derived contract"));
+		input.push_front(list<ContractDefinition const*>(basesBases.begin(), basesBases.end()));
+	}
+	vector<ContractDefinition const*> result = cThreeMerge(input);
+	if (result.empty())
+		BOOST_THROW_EXCEPTION(_contract.createTypeError("Linearization of inheritance graph impossible"));
+	_contract.setLinearizedBaseContracts(result);
+}
+
+template <class _T>
+vector<_T const*> NameAndTypeResolver::cThreeMerge(list<list<_T const*>>& _toMerge)
+{
+	// returns true iff _candidate appears only as last element of the lists
+	auto appearsOnlyAtHead = [&](_T const* _candidate) -> bool
+	{
+		for (list<_T const*> const& bases: _toMerge)
+		{
+			solAssert(!bases.empty(), "");
+			if (find(++bases.begin(), bases.end(), _candidate) != bases.end())
+				return false;
+		}
+		return true;
+	};
+	// returns the next candidate to append to the linearized list or nullptr on failure
+	auto nextCandidate = [&]() -> _T const*
+	{
+		for (list<_T const*> const& bases: _toMerge)
+		{
+			solAssert(!bases.empty(), "");
+			if (appearsOnlyAtHead(bases.front()))
+				return bases.front();
+		}
+		return nullptr;
+	};
+	// removes the given contract from all lists
+	auto removeCandidate = [&](_T const* _candidate)
+	{
+		for (auto it = _toMerge.begin(); it != _toMerge.end();)
+		{
+			it->remove(_candidate);
+			if (it->empty())
+				it = _toMerge.erase(it);
+			else
+				++it;
+		}
+	};
+
+	_toMerge.remove_if([](list<_T const*> const& _bases) { return _bases.empty(); });
+	vector<_T const*> result;
+	while (!_toMerge.empty())
+	{
+		_T const* candidate = nextCandidate();
+		if (!candidate)
+			return vector<_T const*>();
+		result.push_back(candidate);
+		removeCandidate(candidate);
+	}
+	return result;
+}
+
 DeclarationRegistrationHelper::DeclarationRegistrationHelper(map<ASTNode const*, DeclarationContainer>& _scopes,
 															 ASTNode& _astRoot):
 	m_scopes(_scopes), m_currentScope(nullptr)
diff --git a/NameAndTypeResolver.h b/NameAndTypeResolver.h
index 1032a87c..4fb67da3 100644
--- a/NameAndTypeResolver.h
+++ b/NameAndTypeResolver.h
@@ -23,6 +23,7 @@
 #pragma once
 
 #include <map>
+#include <list>
 #include <boost/noncopyable.hpp>
 
 #include <libsolidity/DeclarationContainer.h>
@@ -64,6 +65,17 @@ public:
 private:
 	void reset();
 
+	/// Imports all members declared directly in the given contract (i.e. does not import inherited
+	/// members) into the current scope if they are not present already.
+	void importInheritedScope(ContractDefinition const& _base);
+
+	/// Computes "C3-Linearization" of base contracts and stores it inside the contract.
+	void linearizeBaseContracts(ContractDefinition& _contract) const;
+	/// Computes the C3-merge of the given list of lists of bases.
+	/// @returns the linearized vector or an empty vector if linearization is not possible.
+	template <class _T>
+	static std::vector<_T const*> cThreeMerge(std::list<std::list<_T const*>>& _toMerge);
+
 	/// Maps nodes declaring a scope to scopes, i.e. ContractDefinition and FunctionDeclaration,
 	/// where nullptr denotes the global scope. Note that structs are not scope since they do
 	/// not contain code.