Merge pull request #522 from chriseth/inline2

Allow calling internal functions of libraries.

7 files changed, 299 insertions, 61 deletions

diff --git a/docs/contracts.rst b/docs/contracts.rst
index 2ab03849..9923b1d2 100644
--- a/docs/contracts.rst
+++ b/docs/contracts.rst
@@ -697,6 +697,18 @@ accessed. As a library is an isolated piece of source code, it can only access
 state variables of the calling contract if they are explicitly supplied (it
 would have to way to name them, otherwise).
 
+Libraries can be seen as implicit base contracts of the contracts that use them.
+They will not be explicitly visible in the inheritance hierarchy, but calls
+to library functions look just like calls to functions of explicit base
+contracts (`L.f()` if `L` is the name of the library). Furthermore,
+`internal` functions of libraries are visible in all contracts, just as
+if the library were a base contract. Of course, calls to internal functions
+use the internal calling convention, which means that all internal types
+can be passed and memory types will be passed by reference and not copied.
+In order to realise this in the EVM, code of internal library functions
+(and all functions called from therein) will be pulled into the calling
+contract and a regular `JUMP` call will be used instead of a `DELEGATECALL`.
+
 .. index:: using for, set
 
 The following example illustrates how to use libraries (but
@@ -763,6 +775,60 @@ actual external function call is performed.
 in this call, though (prior to Homestead, `msg.sender` and
 `msg.value` changed, though).
 
+The following example shows how to use memory types and
+internal functions in libraries in order to implement
+custom types without the overhead of external function calls:
+
+::
+
+	library bigint {
+		struct bigint {
+		    uint[] limbs;
+		}
+		function fromUint(uint x) internal returns (bigint r) {
+		    r.limbs = new uint[](1);
+		    r.limbs[0] = x;
+		}
+		function add(bigint _a, bigint _b) internal returns (bigint r) {
+		    r.limbs = new uint[](max(_a.limbs.length, _b.limbs.length));
+		    uint carry = 0;
+		    for (uint i = 0; i < r.limbs.length; ++i) {
+		        uint a = limb(_a, i);
+		        uint b = limb(_b, i);
+		        r.limbs[i] = a + b + carry;
+		        if (a + b < a || (a + b == uint(-1) && carry > 0))
+		            carry = 1;
+		        else
+		            carry = 0;
+		    }
+		    if (carry > 0) {
+		        // too bad, we have to add a limb
+		        uint[] memory newLimbs = new uint[](r.limbs.length + 1);
+		        for (i = 0; i < r.limbs.length; ++i)
+		            newLimbs[i] = r.limbs[i];
+		        newLimbs[i] = carry;
+		        r.limbs = newLimbs;
+		    }
+		}
+
+		function limb(bigint _a, uint _limb) internal returns (uint) {
+		    return _limb < _a.limbs.length ? _a.limbs[_limb] : 0;
+		}
+
+		function max(uint a, uint b) private returns (uint) {
+		    return a > b ? a : b;
+		}
+	}
+
+	contract C {
+		using bigint for bigint.bigint;
+		function f() {
+		    var x = bigint.fromUint(7);
+		    var y = bigint.fromUint(uint(-1));
+		    var z = x.add(y);
+		}
+	}
+
 As the compiler cannot know where the library will be
 deployed at, these addresses have to be filled into the
 final bytecode by a linker (see [Using the Commandline
diff --git a/libsolidity/ast/Types.cpp b/libsolidity/ast/Types.cpp
index 4dc1eb13..d541de23 100644
--- a/libsolidity/ast/Types.cpp
+++ b/libsolidity/ast/Types.cpp
@@ -197,7 +197,7 @@ MemberList const& Type::members(ContractDefinition const* _currentScope) const
 	{
 		MemberList::MemberMap members = nativeMembers(_currentScope);
 		if (_currentScope)
-			members +=  boundFunctions(*this, *_currentScope);
+			members += boundFunctions(*this, *_currentScope);
 		m_members[_currentScope] = unique_ptr<MemberList>(new MemberList(move(members)));
 	}
 	return *m_members[_currentScope];
@@ -220,19 +220,14 @@ MemberList::MemberMap Type::boundFunctions(Type const& _type, ContractDefinition
 			auto const& library = dynamic_cast<ContractDefinition const&>(
 				*ufd->libraryName().annotation().referencedDeclaration
 			);
-			for (auto const& it: library.interfaceFunctions())
+			for (FunctionDefinition const* function: library.definedFunctions())
 			{
-				FunctionType const& funType = *it.second;
-				solAssert(funType.hasDeclaration(), "Tried to bind function without declaration.");
-				if (seenFunctions.count(&funType.declaration()))
+				if (!function->isVisibleInDerivedContracts() || seenFunctions.count(function))
 					continue;
-				seenFunctions.insert(&funType.declaration());
+				seenFunctions.insert(function);
+				FunctionType funType(*function, false);
 				if (auto fun = funType.asMemberFunction(true, true))
-					members.push_back(MemberList::Member(
-						funType.declaration().name(),
-						fun,
-						&funType.declaration()
-					));
+					members.push_back(MemberList::Member(function->name(), fun, function));
 			}
 		}
 	return members;
@@ -1052,7 +1047,7 @@ MemberList::MemberMap ContractType::nativeMembers(ContractDefinition const*) con
 					));
 			}
 	}
-	else
+	else if (!m_contract.isLibrary())
 	{
 		for (auto const& it: m_contract.interfaceFunctions())
 			members.push_back(MemberList::Member(
@@ -1772,21 +1767,40 @@ FunctionTypePointer FunctionType::asMemberFunction(bool _inLibrary, bool _bound)
 			parameterTypes.push_back(t);
 	}
 
-	// Removes dynamic types.
+	Location location = m_location;
+	if (_inLibrary)
+	{
+		solAssert(!!m_declaration, "Declaration has to be available.");
+		if (!m_declaration->isPublic())
+			location = Location::Internal; // will be inlined
+		else
+			location = Location::DelegateCall;
+	}
+
 	TypePointers returnParameterTypes;
 	vector<string> returnParameterNames;
-	for (size_t i = 0; i < m_returnParameterTypes.size(); ++i)
-		if (!m_returnParameterTypes[i]->isDynamicallySized())
-		{
-			returnParameterTypes.push_back(m_returnParameterTypes[i]);
-			returnParameterNames.push_back(m_returnParameterNames[i]);
-		}
+	if (location == Location::Internal)
+	{
+		returnParameterNames = m_returnParameterNames;
+		returnParameterTypes = m_returnParameterTypes;
+	}
+	else
+	{
+		// Removes dynamic types.
+		for (size_t i = 0; i < m_returnParameterTypes.size(); ++i)
+			if (!m_returnParameterTypes[i]->isDynamicallySized())
+			{
+				returnParameterTypes.push_back(m_returnParameterTypes[i]);
+				returnParameterNames.push_back(m_returnParameterNames[i]);
+			}
+	}
+
 	return make_shared<FunctionType>(
 		parameterTypes,
 		returnParameterTypes,
 		m_parameterNames,
 		returnParameterNames,
-		_inLibrary ? Location::DelegateCall : m_location,
+		location,
 		m_arbitraryParameters,
 		m_declaration,
 		m_gasSet,
@@ -1882,12 +1896,13 @@ MemberList::MemberMap TypeType::nativeMembers(ContractDefinition const* _current
 			isBase = (find(currentBases.begin(), currentBases.end(), &contract) != currentBases.end());
 		}
 		if (contract.isLibrary())
-			for (auto const& it: contract.interfaceFunctions())
-				members.push_back(MemberList::Member(
-					it.second->declaration().name(),
-					it.second->asMemberFunction(true),
-					&it.second->declaration()
-				));
+			for (FunctionDefinition const* function: contract.definedFunctions())
+				if (function->isVisibleInDerivedContracts())
+					members.push_back(MemberList::Member(
+						function->name(),
+						FunctionType(*function).asMemberFunction(true),
+						function
+					));
 		if (isBase)
 		{
 			// We are accessing the type of a base contract, so add all public and protected
diff --git a/libsolidity/codegen/CompilerContext.cpp b/libsolidity/codegen/CompilerContext.cpp
index 53c2da05..c1dc8dfb 100644
--- a/libsolidity/codegen/CompilerContext.cpp
+++ b/libsolidity/codegen/CompilerContext.cpp
@@ -91,6 +91,12 @@ eth::AssemblyItem CompilerContext::functionEntryLabelIfExists(Declaration const&
 
 eth::AssemblyItem CompilerContext::virtualFunctionEntryLabel(FunctionDefinition const& _function)
 {
+	// Libraries do not allow inheritance and their functions can be inlined, so we should not
+	// search the inheritance hierarchy (which will be the wrong one in case the function
+	// is inlined).
+	if (auto scope = dynamic_cast<ContractDefinition const*>(_function.scope()))
+		if (scope->isLibrary())
+			return functionEntryLabel(_function);
 	solAssert(!m_inheritanceHierarchy.empty(), "No inheritance hierarchy set.");
 	return virtualFunctionEntryLabel(_function, m_inheritanceHierarchy.begin());
 }
diff --git a/libsolidity/codegen/ExpressionCompiler.cpp b/libsolidity/codegen/ExpressionCompiler.cpp
index d1cbc8ed..ab02e0b5 100644
--- a/libsolidity/codegen/ExpressionCompiler.cpp
+++ b/libsolidity/codegen/ExpressionCompiler.cpp
@@ -464,8 +464,8 @@ bool ExpressionCompiler::visit(FunctionCall const& _functionCall)
 	{
 		FunctionType const& function = *functionType;
 		if (function.bound())
-			// Only delegatecall functions can be bound, this might be lifted later.
-			solAssert(function.location() == Location::DelegateCall, "");
+			// Only delegatecall and internal functions can be bound, this might be lifted later.
+			solAssert(function.location() == Location::DelegateCall || function.location() == Location::Internal, "");
 		switch (function.location())
 		{
 		case Location::Internal:
@@ -480,13 +480,21 @@ bool ExpressionCompiler::visit(FunctionCall const& _functionCall)
 				utils().convertType(*arguments[i]->annotation().type, *function.parameterTypes()[i]);
 			}
 			_functionCall.expression().accept(*this);
+			unsigned parameterSize = CompilerUtils::sizeOnStack(function.parameterTypes());
+			if (function.bound())
+			{
+				// stack: arg2, ..., argn, label, arg1
+				unsigned depth = parameterSize + 1;
+				utils().moveIntoStack(depth, function.selfType()->sizeOnStack());
+				parameterSize += function.selfType()->sizeOnStack();
+			}
 
 			m_context.appendJump(eth::AssemblyItem::JumpType::IntoFunction);
 			m_context << returnLabel;
 
 			unsigned returnParametersSize = CompilerUtils::sizeOnStack(function.returnParameterTypes());
 			// callee adds return parameters, but removes arguments and return label
-			m_context.adjustStackOffset(returnParametersSize - CompilerUtils::sizeOnStack(function.parameterTypes()) - 1);
+			m_context.adjustStackOffset(returnParametersSize - parameterSize - 1);
 			break;
 		}
 		case Location::External:
@@ -809,7 +817,7 @@ bool ExpressionCompiler::visit(NewExpression const&)
 	return false;
 }
 
-void ExpressionCompiler::endVisit(MemberAccess const& _memberAccess)
+bool ExpressionCompiler::visit(MemberAccess const& _memberAccess)
 {
 	CompilerContext::LocationSetter locationSetter(m_context, _memberAccess);
 	// Check whether the member is a bound function.
@@ -817,19 +825,68 @@ void ExpressionCompiler::endVisit(MemberAccess const& _memberAccess)
 	if (auto funType = dynamic_cast<FunctionType const*>(_memberAccess.annotation().type.get()))
 		if (funType->bound())
 		{
+			_memberAccess.expression().accept(*this);
 			utils().convertType(
 				*_memberAccess.expression().annotation().type,
 				*funType->selfType(),
 				true
 			);
-			auto contract = dynamic_cast<ContractDefinition const*>(funType->declaration().scope());
-			solAssert(contract && contract->isLibrary(), "");
-			m_context.appendLibraryAddress(contract->name());
-			m_context << funType->externalIdentifier();
-			utils().moveIntoStack(funType->selfType()->sizeOnStack(), 2);
-			return;
+			if (funType->location() == FunctionType::Location::Internal)
+			{
+				m_context << m_context.functionEntryLabel(
+					dynamic_cast<FunctionDefinition const&>(funType->declaration())
+				).pushTag();
+				utils().moveIntoStack(funType->selfType()->sizeOnStack(), 1);
+			}
+			else
+			{
+				solAssert(funType->location() == FunctionType::Location::DelegateCall, "");
+				auto contract = dynamic_cast<ContractDefinition const*>(funType->declaration().scope());
+				solAssert(contract && contract->isLibrary(), "");
+				m_context.appendLibraryAddress(contract->name());
+				m_context << funType->externalIdentifier();
+				utils().moveIntoStack(funType->selfType()->sizeOnStack(), 2);
+			}
+			return false;
 		}
 
+	// Special processing for TypeType because we do not want to visit the library itself
+	// for internal functions.
+	if (TypeType const* type = dynamic_cast<TypeType const*>(_memberAccess.expression().annotation().type.get()))
+	{
+		if (dynamic_cast<ContractType const*>(type->actualType().get()))
+		{
+			if (auto funType = dynamic_cast<FunctionType const*>(_memberAccess.annotation().type.get()))
+			{
+				if (funType->location() != FunctionType::Location::Internal)
+				{
+					_memberAccess.expression().accept(*this);
+					m_context << funType->externalIdentifier();
+				}
+				else
+				{
+					// We do not visit the expression here on purpose, because in the case of an
+					// internal library function call, this would push the library address forcing
+					// us to link against it although we actually do not need it.
+					auto const* function = dynamic_cast<FunctionDefinition const*>(_memberAccess.annotation().referencedDeclaration);
+					solAssert(!!function, "Function not found in member access");
+					m_context << m_context.functionEntryLabel(*function).pushTag();
+				}
+			}
+			else
+				_memberAccess.expression().accept(*this);
+		}
+		else if (auto enumType = dynamic_cast<EnumType const*>(type->actualType().get()))
+		{
+			_memberAccess.expression().accept(*this);
+			m_context << enumType->memberValue(_memberAccess.memberName());
+		}
+		else
+			_memberAccess.expression().accept(*this);
+		return false;
+	}
+
+	_memberAccess.expression().accept(*this);
 	switch (_memberAccess.expression().annotation().type->category())
 	{
 	case Type::Category::Contract:
@@ -948,28 +1005,6 @@ void ExpressionCompiler::endVisit(MemberAccess const& _memberAccess)
 		m_context << type.memberValue(_memberAccess.memberName());
 		break;
 	}
-	case Type::Category::TypeType:
-	{
-		TypeType const& type = dynamic_cast<TypeType const&>(*_memberAccess.expression().annotation().type);
-
-		if (dynamic_cast<ContractType const*>(type.actualType().get()))
-		{
-			if (auto funType = dynamic_cast<FunctionType const*>(_memberAccess.annotation().type.get()))
-			{
-				if (funType->location() != FunctionType::Location::Internal)
-					m_context << funType->externalIdentifier();
-				else
-				{
-					auto const* function = dynamic_cast<FunctionDefinition const*>(_memberAccess.annotation().referencedDeclaration);
-					solAssert(!!function, "Function not found in member access");
-					m_context << m_context.functionEntryLabel(*function).pushTag();
-				}
-			}
-		}
-		else if (auto enumType = dynamic_cast<EnumType const*>(type.actualType().get()))
-			m_context << enumType->memberValue(_memberAccess.memberName());
-		break;
-	}
 	case Type::Category::Array:
 	{
 		auto const& type = dynamic_cast<ArrayType const&>(*_memberAccess.expression().annotation().type);
@@ -1018,6 +1053,7 @@ void ExpressionCompiler::endVisit(MemberAccess const& _memberAccess)
 	default:
 		BOOST_THROW_EXCEPTION(InternalCompilerError() << errinfo_comment("Member access to unknown type."));
 	}
+	return false;
 }
 
 bool ExpressionCompiler::visit(IndexAccess const& _indexAccess)
diff --git a/libsolidity/codegen/ExpressionCompiler.h b/libsolidity/codegen/ExpressionCompiler.h
index f00b24e8..43a92a10 100644
--- a/libsolidity/codegen/ExpressionCompiler.h
+++ b/libsolidity/codegen/ExpressionCompiler.h
@@ -78,7 +78,7 @@ private:
 	virtual bool visit(BinaryOperation const& _binaryOperation) override;
 	virtual bool visit(FunctionCall const& _functionCall) override;
 	virtual bool visit(NewExpression const& _newExpression) override;
-	virtual void endVisit(MemberAccess const& _memberAccess) override;
+	virtual bool visit(MemberAccess const& _memberAccess) override;
 	virtual bool visit(IndexAccess const& _indexAccess) override;
 	virtual void endVisit(Identifier const& _identifier) override;
 	virtual void endVisit(Literal const& _literal) override;
diff --git a/test/libsolidity/SolidityEndToEndTest.cpp b/test/libsolidity/SolidityEndToEndTest.cpp
index f9d2ab2b..9df64cdc 100644
--- a/test/libsolidity/SolidityEndToEndTest.cpp
+++ b/test/libsolidity/SolidityEndToEndTest.cpp
@@ -6633,6 +6633,108 @@ BOOST_AUTO_TEST_CASE(delete_on_array_of_structs)
 	BOOST_CHECK(callContractFunction("f()") == encodeArgs(true));
 }
 
+BOOST_AUTO_TEST_CASE(internal_library_function)
+{
+	// tests that internal library functions can be called from outside
+	// and retain the same memory context (i.e. are pulled into the caller's code)
+	char const* sourceCode = R"(
+		library L {
+			function f(uint[] _data) internal {
+				_data[3] = 2;
+			}
+		}
+		contract C {
+			function f() returns (uint) {
+				uint[] memory x = new uint[](7);
+				x[3] = 8;
+				L.f(x);
+				return x[3];
+			}
+		}
+	)";
+	// This has to work without linking, because everything will be inlined.
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f()") == encodeArgs(u256(2)));
+}
+
+BOOST_AUTO_TEST_CASE(internal_library_function_calling_private)
+{
+	// tests that internal library functions that are called from outside and that
+	// themselves call private functions are still able to (i.e. the private function
+	// also has to be pulled into the caller's code)
+	char const* sourceCode = R"(
+		library L {
+			function g(uint[] _data) private {
+				_data[3] = 2;
+			}
+			function f(uint[] _data) internal {
+				g(_data);
+			}
+		}
+		contract C {
+			function f() returns (uint) {
+				uint[] memory x = new uint[](7);
+				x[3] = 8;
+				L.f(x);
+				return x[3];
+			}
+		}
+	)";
+	// This has to work without linking, because everything will be inlined.
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f()") == encodeArgs(u256(2)));
+}
+
+BOOST_AUTO_TEST_CASE(internal_library_function_bound)
+{
+	char const* sourceCode = R"(
+		library L {
+			struct S { uint[] data; }
+			function f(S _s) internal {
+				_s.data[3] = 2;
+			}
+		}
+		contract C {
+			using L for L.S;
+			function f() returns (uint) {
+				L.S memory x;
+				x.data = new uint[](7);
+				x.data[3] = 8;
+				x.f();
+				return x.data[3];
+			}
+		}
+	)";
+	// This has to work without linking, because everything will be inlined.
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f()") == encodeArgs(u256(2)));
+}
+
+BOOST_AUTO_TEST_CASE(internal_library_function_return_var_size)
+{
+	char const* sourceCode = R"(
+		library L {
+			struct S { uint[] data; }
+			function f(S _s) internal returns (uint[]) {
+				_s.data[3] = 2;
+				return _s.data;
+			}
+		}
+		contract C {
+			using L for L.S;
+			function f() returns (uint) {
+				L.S memory x;
+				x.data = new uint[](7);
+				x.data[3] = 8;
+				return x.f()[3];
+			}
+		}
+	)";
+	// This has to work without linking, because everything will be inlined.
+	compileAndRun(sourceCode, 0, "C");
+	BOOST_CHECK(callContractFunction("f()") == encodeArgs(u256(2)));
+}
+
 BOOST_AUTO_TEST_SUITE_END()
 
 }
diff --git a/test/libsolidity/SolidityNameAndTypeResolution.cpp b/test/libsolidity/SolidityNameAndTypeResolution.cpp
index b6e21d0f..9c411781 100644
--- a/test/libsolidity/SolidityNameAndTypeResolution.cpp
+++ b/test/libsolidity/SolidityNameAndTypeResolution.cpp
@@ -2323,12 +2323,11 @@ BOOST_AUTO_TEST_CASE(call_to_library_function)
 {
 	char const* text = R"(
 		library Lib {
-			uint constant public pimil = 3141592;
 			function min(uint x, uint y) returns (uint);
 		}
 		contract Test {
 			function f() {
-				uint t = Lib.min(Lib.pimil(), 7);
+				uint t = Lib.min(12, 7);
 			}
 		}
 	)";
@@ -3257,6 +3256,20 @@ BOOST_AUTO_TEST_CASE(library_functions_do_not_have_value)
 	BOOST_CHECK(!success(text));
 }
 
+BOOST_AUTO_TEST_CASE(library_instances_cannot_be_used)
+{
+	char const* text = R"(
+		library L { function l() {} }
+		contract test {
+			function f() {
+				L x;
+				x.l();
+			}
+		}
+	)";
+	BOOST_CHECK(!success(text));
+}
+
 BOOST_AUTO_TEST_CASE(invalid_fixed_type_long)
 {
 	char const* text = R"(