Perform stack height checks in assembly analysis phase.

3 files changed, 148 insertions, 37 deletions

diff --git a/libsolidity/inlineasm/AsmAnalysis.cpp b/libsolidity/inlineasm/AsmAnalysis.cpp
index 29016ef9..e989560d 100644
--- a/libsolidity/inlineasm/AsmAnalysis.cpp
+++ b/libsolidity/inlineasm/AsmAnalysis.cpp
@@ -51,11 +51,20 @@ bool AsmAnalyzer::analyze(Block const& _block)
 {
 	if (!(ScopeFiller(m_scopes, m_errors))(_block))
 		return false;
+
 	return (*this)(_block);
 }
 
+bool AsmAnalyzer::operator()(assembly::Instruction const& _instruction)
+{
+	auto const& info = instructionInfo(_instruction.instruction);
+	m_stackHeight += info.ret - info.args;
+	return true;
+}
+
 bool AsmAnalyzer::operator()(assembly::Literal const& _literal)
 {
+	++m_stackHeight;
 	if (!_literal.isNumber && _literal.value.size() > 32)
 	{
 		m_errors.push_back(make_shared<Error>(
@@ -83,8 +92,12 @@ bool AsmAnalyzer::operator()(assembly::Identifier const& _identifier)
 				));
 				success = false;
 			}
+			++m_stackHeight;
+		},
+		[&](Scope::Label const&)
+		{
+			++m_stackHeight;
 		},
-		[&](Scope::Label const&) {},
 		[&](Scope::Function const&)
 		{
 			m_errors.push_back(make_shared<Error>(
@@ -97,14 +110,21 @@ bool AsmAnalyzer::operator()(assembly::Identifier const& _identifier)
 	)))
 	{
 	}
-	else if (!m_resolver || m_resolver(_identifier, IdentifierContext::RValue) == size_t(-1))
+	else
 	{
-		m_errors.push_back(make_shared<Error>(
-			Error::Type::DeclarationError,
-			"Identifier not found.",
-			_identifier.location
-		));
-		success = false;
+		size_t stackSize(-1);
+		if (m_resolver)
+			stackSize = m_resolver(_identifier, IdentifierContext::RValue);
+		if (stackSize == size_t(-1))
+		{
+			m_errors.push_back(make_shared<Error>(
+				Error::Type::DeclarationError,
+				"Identifier not found.",
+				_identifier.location
+			));
+			success = false;
+		}
+		m_stackHeight += stackSize == size_t(-1) ? 1 : stackSize;
 	}
 	return success;
 }
@@ -113,8 +133,14 @@ bool AsmAnalyzer::operator()(FunctionalInstruction const& _instr)
 {
 	bool success = true;
 	for (auto const& arg: _instr.arguments | boost::adaptors::reversed)
+	{
+		int const stackHeight = m_stackHeight;
 		if (!boost::apply_visitor(*this, arg))
 			success = false;
+		if (!expectDeposit(1, stackHeight, locationOf(arg)))
+			success = false;
+	}
+	// Parser already checks that the number of arguments is correct.
 	if (!(*this)(_instr.instruction))
 		success = false;
 	return success;
@@ -122,13 +148,15 @@ bool AsmAnalyzer::operator()(FunctionalInstruction const& _instr)
 
 bool AsmAnalyzer::operator()(assembly::Assignment const& _assignment)
 {
-	return checkAssignment(_assignment.variableName);
+	return checkAssignment(_assignment.variableName, size_t(-1));
 }
 
 bool AsmAnalyzer::operator()(FunctionalAssignment const& _assignment)
 {
+	int const stackHeight = m_stackHeight;
 	bool success = boost::apply_visitor(*this, *_assignment.value);
-	if (!checkAssignment(_assignment.variableName))
+	solAssert(m_stackHeight >= stackHeight, "Negative value size.");
+	if (!checkAssignment(_assignment.variableName, m_stackHeight - stackHeight))
 		success = false;
 	return success;
 }
@@ -146,7 +174,14 @@ bool AsmAnalyzer::operator()(assembly::FunctionDefinition const& _funDef)
 	for (auto const& var: _funDef.arguments + _funDef.returns)
 		boost::get<Scope::Variable>(bodyScope.identifiers.at(var)).active = true;
 
-	return (*this)(_funDef.body);
+	int const stackHeight = m_stackHeight;
+	m_stackHeight = _funDef.arguments.size() + _funDef.returns.size();
+	m_virtualVariablesInNextBlock = m_stackHeight;
+
+	bool success = (*this)(_funDef.body);
+
+	m_stackHeight = stackHeight;
+	return success;
 }
 
 bool AsmAnalyzer::operator()(assembly::FunctionCall const& _funCall)
@@ -202,12 +237,16 @@ bool AsmAnalyzer::operator()(assembly::FunctionCall const& _funCall)
 				));
 			success = false;
 		}
-		//@todo check the number of returns - depends on context and should probably
-		// be only done once we have stack height checks
 	}
 	for (auto const& arg: _funCall.arguments | boost::adaptors::reversed)
+	{
+		int const stackHeight = m_stackHeight;
 		if (!boost::apply_visitor(*this, arg))
 			success = false;
+		if (!expectDeposit(1, stackHeight, locationOf(arg)))
+			success = false;
+	}
+	m_stackHeight += returns - arguments;
 	return success;
 }
 
@@ -216,19 +255,42 @@ bool AsmAnalyzer::operator()(Block const& _block)
 	bool success = true;
 	m_currentScope = &scope(&_block);
 
+	int const virtualVariablesInNextBlock = m_virtualVariablesInNextBlock;
+	m_virtualVariablesInNextBlock = 0;
+	int const initialStackHeight = m_stackHeight;
+
 	for (auto const& s: _block.statements)
 		if (!boost::apply_visitor(*this, s))
 			success = false;
 
+	for (auto const& identifier: scope(&_block).identifiers)
+		if (identifier.second.type() == typeid(Scope::Variable))
+			--m_stackHeight;
+
+	int const stackDiff = m_stackHeight - initialStackHeight + virtualVariablesInNextBlock;
+	if (stackDiff != 0)
+	{
+		m_errors.push_back(make_shared<Error>(
+			Error::Type::DeclarationError,
+			"Unbalanced stack at the end of a block: " +
+			(
+				stackDiff > 0 ?
+				to_string(stackDiff) + string(" surplus item(s).") :
+				to_string(-stackDiff) + string(" missing item(s).")
+			),
+			_block.location
+		));
+		success = false;
+	}
+
 	m_currentScope = m_currentScope->superScope;
 	return success;
 }
 
-bool AsmAnalyzer::checkAssignment(assembly::Identifier const& _variable)
+bool AsmAnalyzer::checkAssignment(assembly::Identifier const& _variable, size_t _valueSize)
 {
-	if (!(*this)(_variable))
-		return false;
-
+	bool success = true;
+	size_t variableSize(-1);
 	if (Scope::Identifier const* var = m_currentScope->lookup(_variable.name))
 	{
 		// Check that it is a variable
@@ -239,19 +301,69 @@ bool AsmAnalyzer::checkAssignment(assembly::Identifier const& _variable)
 				"Assignment requires variable.",
 				_variable.location
 			));
-			return false;
+			success = false;
 		}
+		else if (!boost::get<Scope::Variable>(*var).active)
+		{
+			m_errors.push_back(make_shared<Error>(
+				Error::Type::DeclarationError,
+				"Variable " + _variable.name + " used before it was declared.",
+				_variable.location
+			));
+			success = false;
+		}
+		variableSize = 1;
 	}
-	else if (!m_resolver || m_resolver(_variable, IdentifierContext::LValue) == size_t(-1))
+	else if (m_resolver)
+		variableSize = m_resolver(_variable, IdentifierContext::LValue);
+	if (variableSize == size_t(-1))
 	{
 		m_errors.push_back(make_shared<Error>(
 			Error::Type::DeclarationError,
-			"Variable not found.",
+			"Variable not found or variable not lvalue.",
 			_variable.location
 		));
+		success = false;
+	}
+	if (_valueSize == size_t(-1))
+		_valueSize = variableSize == size_t(-1) ? 1 : variableSize;
+
+	m_stackHeight -= _valueSize;
+
+	if (_valueSize != variableSize && variableSize != size_t(-1))
+	{
+		m_errors.push_back(make_shared<Error>(
+			Error::Type::TypeError,
+			"Variable size (" +
+			to_string(variableSize) +
+			") and value size (" +
+			to_string(_valueSize) +
+			") do not match.",
+			_variable.location
+		));
+		success = false;
+	}
+	return success;
+}
+
+bool AsmAnalyzer::expectDeposit(int const _deposit, int const _oldHeight, SourceLocation const& _location)
+{
+	int stackDiff = m_stackHeight - _oldHeight;
+	if (stackDiff != _deposit)
+	{
+		m_errors.push_back(make_shared<Error>(
+			Error::Type::TypeError,
+			"Expected instruction(s) to deposit " +
+			boost::lexical_cast<string>(_deposit) +
+			" item(s) to the stack, but did deposit " +
+			boost::lexical_cast<string>(stackDiff) +
+			" item(s).",
+			_location
+		));
 		return false;
 	}
-	return true;
+	else
+		return true;
 }
 
 Scope& AsmAnalyzer::scope(Block const* _block)
diff --git a/libsolidity/inlineasm/AsmAnalysis.h b/libsolidity/inlineasm/AsmAnalysis.h
index c6d23227..cfc9b25a 100644
--- a/libsolidity/inlineasm/AsmAnalysis.h
+++ b/libsolidity/inlineasm/AsmAnalysis.h
@@ -53,7 +53,7 @@ struct Scope;
 /**
  * Performs the full analysis stage, calls the ScopeFiller internally, then resolves
  * references and performs other checks.
- * @todo Does not yet check for stack height issues.
+ * If all these checks pass, code generation should not throw errors.
  */
 class AsmAnalyzer: public boost::static_visitor<bool>
 {
@@ -63,7 +63,7 @@ public:
 
 	bool analyze(assembly::Block const& _block);
 
-	bool operator()(assembly::Instruction const&) { return true; }
+	bool operator()(assembly::Instruction const&);
 	bool operator()(assembly::Literal const& _literal);
 	bool operator()(assembly::Identifier const&);
 	bool operator()(assembly::FunctionalInstruction const& _functionalInstruction);
@@ -76,9 +76,16 @@ public:
 	bool operator()(assembly::Block const& _block);
 
 private:
-	bool checkAssignment(assembly::Identifier const& _assignment);
+	/// Verifies that a variable to be assigned to exists and has the same size
+	/// as the value, @a _valueSize, unless that is equal to -1.
+	bool checkAssignment(assembly::Identifier const& _assignment, size_t _valueSize = size_t(-1));
+	bool expectDeposit(int _deposit, int _oldHeight, SourceLocation const& _location);
 	Scope& scope(assembly::Block const* _block);
 
+	/// Number of excess stack slots generated by function arguments to take into account for
+	/// next block.
+	int m_virtualVariablesInNextBlock = 0;
+	int m_stackHeight = 0;
 	ExternalIdentifierAccess::Resolver const& m_resolver;
 	Scope* m_currentScope = nullptr;
 	Scopes& m_scopes;
diff --git a/libsolidity/inlineasm/AsmCodeGen.cpp b/libsolidity/inlineasm/AsmCodeGen.cpp
index c1efa292..a79c5a37 100644
--- a/libsolidity/inlineasm/AsmCodeGen.cpp
+++ b/libsolidity/inlineasm/AsmCodeGen.cpp
@@ -185,7 +185,7 @@ public:
 		{
 			int height = m_state.assembly.deposit();
 			boost::apply_visitor(*this, *it);
-			expectDeposit(1, height, locationOf(*it));
+			expectDeposit(1, height);
 		}
 		(*this)(_instr.instruction);
 	}
@@ -210,7 +210,7 @@ public:
 	{
 		int height = m_state.assembly.deposit();
 		boost::apply_visitor(*this, *_assignment.value);
-		expectDeposit(1, height, locationOf(*_assignment.value));
+		expectDeposit(1, height);
 		m_state.assembly.setSourceLocation(_assignment.location);
 		generateAssignment(_assignment.variableName, _assignment.location);
 	}
@@ -218,7 +218,7 @@ public:
 	{
 		int height = m_state.assembly.deposit();
 		boost::apply_visitor(*this, *_varDecl.value);
-		expectDeposit(1, height, locationOf(*_varDecl.value));
+		expectDeposit(1, height);
 		auto& var = boost::get<Scope::Variable>(m_scope.identifiers.at(_varDecl.name));
 		var.stackHeight = height;
 		var.active = true;
@@ -279,17 +279,9 @@ private:
 			return heightDiff;
 	}
 
-	void expectDeposit(int _deposit, int _oldHeight, SourceLocation const& _location)
+	void expectDeposit(int _deposit, int _oldHeight)
 	{
-		if (m_state.assembly.deposit() != _oldHeight + 1)
-			m_state.addError(Error::Type::TypeError,
-				"Expected instruction(s) to deposit " +
-				boost::lexical_cast<string>(_deposit) +
-				" item(s) to the stack, but did deposit " +
-				boost::lexical_cast<string>(m_state.assembly.deposit() - _oldHeight) +
-				" item(s).",
-				_location
-			);
+		solAssert(m_state.assembly.deposit() == _oldHeight + _deposit, "Invalid stack deposit.");
 	}
 
 	/// Assigns the label's id to a value taken from eth::Assembly if it has not yet been set.