Move EVM codegen to libjulia.

3 files changed, 363 insertions, 0 deletions

diff --git a/libjulia/backends/evm/AbstractAssembly.h b/libjulia/backends/evm/AbstractAssembly.h
new file mode 100644
index 00000000..e3afa2b6
--- /dev/null
+++ b/libjulia/backends/evm/AbstractAssembly.h
@@ -0,0 +1,89 @@
+/*
+	This file is part of solidity.
+
+	solidity is free software: you can redistribute it and/or modify
+	it under the terms of the GNU General Public License as published by
+	the Free Software Foundation, either version 3 of the License, or
+	(at your option) any later version.
+
+	solidity is distributed in the hope that it will be useful,
+	but WITHOUT ANY WARRANTY; without even the implied warranty of
+	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+	GNU General Public License for more details.
+
+	You should have received a copy of the GNU General Public License
+	along with solidity.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * @date 2017
+ * Abstract assembly interface, subclasses of which are to be used with the generic
+ * bytecode generator.
+ */
+
+#pragma once
+
+#include <libdevcore/CommonData.h>
+
+#include <functional>
+
+namespace dev
+{
+struct SourceLocation;
+namespace solidity
+{
+enum class Instruction: uint8_t;
+namespace assembly
+{
+struct Instruction;
+struct Identifier;
+}
+}
+namespace julia
+{
+
+class AbstractAssembly
+{
+public:
+	virtual ~AbstractAssembly() {}
+
+	/// Set a new source location valid starting from the next instruction.
+	virtual void setSourceLocation(SourceLocation const& _location) = 0;
+	/// Retrieve the current height of the stack. This does not have to be zero
+	/// at the beginning.
+	virtual int stackHeight() const = 0;
+	/// Append an EVM instruction.
+	virtual void appendInstruction(solidity::Instruction _instruction) = 0;
+	/// Append a constant.
+	virtual void appendConstant(u256 const& _constant) = 0;
+	/// Append a label.
+	virtual void appendLabel(size_t _labelId) = 0;
+	/// Append a label reference.
+	virtual void appendLabelReference(size_t _labelId) = 0;
+	/// Generate a new unique label.
+	virtual size_t newLabelId() = 0;
+	/// Append a reference to a to-be-linked symobl.
+	/// Currently, we assume that the value is always a 20 byte number.
+	virtual void appendLinkerSymbol(std::string const& _name) = 0;
+};
+
+enum class IdentifierContext { LValue, RValue };
+
+/// Object that is used to resolve references and generate code for access to identifiers external
+/// to inline assembly (not used in standalone assembly mode).
+struct ExternalIdentifierAccess
+{
+	using Resolver = std::function<size_t(solidity::assembly::Identifier const&, IdentifierContext)>;
+	/// Resolve a an external reference given by the identifier in the given context.
+	/// @returns the size of the value (number of stack slots) or size_t(-1) if not found.
+	Resolver resolve;
+	using CodeGenerator = std::function<void(solidity::assembly::Identifier const&, IdentifierContext, julia::AbstractAssembly&)>;
+	/// Generate code for retrieving the value (rvalue context) or storing the value (lvalue context)
+	/// of an identifier. The code should be appended to the assembly. In rvalue context, the value is supposed
+	/// to be put onto the stack, in lvalue context, the value is assumed to be at the top of the stack.
+	CodeGenerator generateCode;
+};
+
+
+
+}
+}
diff --git a/libjulia/backends/evm/EVMCodeTransform.cpp b/libjulia/backends/evm/EVMCodeTransform.cpp
new file mode 100644
index 00000000..990df707
--- /dev/null
+++ b/libjulia/backends/evm/EVMCodeTransform.cpp
@@ -0,0 +1,21 @@
+/*
+	This file is part of solidity.
+
+	solidity is free software: you can redistribute it and/or modify
+	it under the terms of the GNU General Public License as published by
+	the Free Software Foundation, either version 3 of the License, or
+	(at your option) any later version.
+
+	solidity is distributed in the hope that it will be useful,
+	but WITHOUT ANY WARRANTY; without even the implied warranty of
+	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+	GNU General Public License for more details.
+
+	You should have received a copy of the GNU General Public License
+	along with solidity.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * Common code generator for translating Julia / inline assembly to EVM and EVM1.5.
+ */
+
+#include <libjulia/backends/evm/EVMCodeGenerator.h>
diff --git a/libjulia/backends/evm/EVMCodeTransform.h b/libjulia/backends/evm/EVMCodeTransform.h
new file mode 100644
index 00000000..ce0fced7
--- /dev/null
+++ b/libjulia/backends/evm/EVMCodeTransform.h
@@ -0,0 +1,253 @@
+/*
+	This file is part of solidity.
+
+	solidity is free software: you can redistribute it and/or modify
+	it under the terms of the GNU General Public License as published by
+	the Free Software Foundation, either version 3 of the License, or
+	(at your option) any later version.
+
+	solidity is distributed in the hope that it will be useful,
+	but WITHOUT ANY WARRANTY; without even the implied warranty of
+	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+	GNU General Public License for more details.
+
+	You should have received a copy of the GNU General Public License
+	along with solidity.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * Common code generator for translating Julia / inline assembly to EVM and EVM1.5.
+ */
+
+
+class CodeTransform: public boost::static_visitor<>
+{
+public:
+	/// Create the code transformer which appends assembly to _state.assembly when called
+	/// with parsed assembly data.
+	/// @param _identifierAccess used to resolve identifiers external to the inline assembly
+	explicit CodeTransform(
+		GeneratorState& _state,
+		julia::AbstractAssembly& _assembly,
+		assembly::Block const& _block,
+		assembly::ExternalIdentifierAccess const& _identifierAccess = assembly::ExternalIdentifierAccess()
+	): CodeTransform(_state, _assembly, _block, _identifierAccess, _assembly.stackHeight())
+	{
+	}
+
+private:
+	CodeTransform(
+		GeneratorState& _state,
+		julia::AbstractAssembly& _assembly,
+		assembly::Block const& _block,
+		assembly::ExternalIdentifierAccess const& _identifierAccess,
+		int _initialStackHeight
+	):
+		m_state(_state),
+		m_assembly(_assembly),
+		m_scope(*m_state.info.scopes.at(&_block)),
+		m_identifierAccess(_identifierAccess),
+		m_initialStackHeight(_initialStackHeight)
+	{
+		int blockStartStackHeight = m_assembly.stackHeight();
+		std::for_each(_block.statements.begin(), _block.statements.end(), boost::apply_visitor(*this));
+
+		m_assembly.setSourceLocation(_block.location);
+
+		// pop variables
+		for (auto const& identifier: m_scope.identifiers)
+			if (identifier.second.type() == typeid(Scope::Variable))
+				m_assembly.appendInstruction(solidity::Instruction::POP);
+
+		int deposit = m_assembly.stackHeight() - blockStartStackHeight;
+		solAssert(deposit == 0, "Invalid stack height at end of block.");
+	}
+
+public:
+	void operator()(assembly::Instruction const& _instruction)
+	{
+		m_assembly.setSourceLocation(_instruction.location);
+		m_assembly.appendInstruction(_instruction.instruction);
+		checkStackHeight(&_instruction);
+	}
+	void operator()(assembly::Literal const& _literal)
+	{
+		m_assembly.setSourceLocation(_literal.location);
+		if (_literal.kind == assembly::LiteralKind::Number)
+			m_assembly.appendConstant(u256(_literal.value));
+		else if (_literal.kind == assembly::LiteralKind::Boolean)
+		{
+			if (_literal.value == "true")
+				m_assembly.appendConstant(u256(1));
+			else
+				m_assembly.appendConstant(u256(0));
+		}
+		else
+		{
+			solAssert(_literal.value.size() <= 32, "");
+			m_assembly.appendConstant(u256(h256(_literal.value, h256::FromBinary, h256::AlignLeft)));
+		}
+		checkStackHeight(&_literal);
+	}
+	void operator()(assembly::Identifier const& _identifier)
+	{
+		m_assembly.setSourceLocation(_identifier.location);
+		// First search internals, then externals.
+		if (m_scope.lookup(_identifier.name, Scope::NonconstVisitor(
+			[=](Scope::Variable& _var)
+			{
+				if (int heightDiff = variableHeightDiff(_var, _identifier.location, false))
+					m_assembly.appendInstruction(solidity::dupInstruction(heightDiff));
+				else
+					// Store something to balance the stack
+					m_assembly.appendConstant(u256(0));
+			},
+			[=](Scope::Label& _label)
+			{
+				assignLabelIdIfUnset(_label);
+				m_assembly.appendLabelReference(*_label.id);
+			},
+			[=](Scope::Function&)
+			{
+				solAssert(false, "Function not removed during desugaring.");
+			}
+		)))
+		{
+			return;
+		}
+		solAssert(
+			m_identifierAccess.generateCode,
+			"Identifier not found and no external access available."
+		);
+		m_identifierAccess.generateCode(_identifier, IdentifierContext::RValue, m_assembly);
+		checkStackHeight(&_identifier);
+	}
+	void operator()(FunctionalInstruction const& _instr)
+	{
+		for (auto it = _instr.arguments.rbegin(); it != _instr.arguments.rend(); ++it)
+		{
+			int height = m_assembly.stackHeight();
+			boost::apply_visitor(*this, *it);
+			expectDeposit(1, height);
+		}
+		(*this)(_instr.instruction);
+		checkStackHeight(&_instr);
+	}
+	void operator()(assembly::FunctionCall const&)
+	{
+		solAssert(false, "Function call not removed during desugaring phase.");
+	}
+	void operator()(Label const& _label)
+	{
+		m_assembly.setSourceLocation(_label.location);
+		solAssert(m_scope.identifiers.count(_label.name), "");
+		Scope::Label& label = boost::get<Scope::Label>(m_scope.identifiers.at(_label.name));
+		assignLabelIdIfUnset(label);
+		m_assembly.appendLabel(*label.id);
+		checkStackHeight(&_label);
+	}
+	void operator()(StackAssignment const& _assignment)
+	{
+		m_assembly.setSourceLocation(_assignment.location);
+		generateAssignment(_assignment.variableName, _assignment.location);
+		checkStackHeight(&_assignment);
+	}
+	void operator()(assembly::Assignment const& _assignment)
+	{
+		int height = m_assembly.stackHeight();
+		boost::apply_visitor(*this, *_assignment.value);
+		expectDeposit(1, height);
+		m_assembly.setSourceLocation(_assignment.location);
+		generateAssignment(_assignment.variableName, _assignment.location);
+		checkStackHeight(&_assignment);
+	}
+	void operator()(assembly::VariableDeclaration const& _varDecl)
+	{
+		int expectedItems = _varDecl.variables.size();
+		boost::apply_visitor(*this, *_varDecl.value);
+		expectDeposit(expectedItems, height);
+		for (auto const& variable: _varDecl.variables)
+		{
+			auto& var = boost::get<Scope::Variable>(m_scope.identifiers.at(variable.name));
+			var.stackHeight = height++;
+			var.active = true;
+		}
+	}
+	void operator()(assembly::Block const& _block)
+	{
+		CodeTransform(m_state, m_assembly, _block, m_identifierAccess, m_initialStackHeight);
+		checkStackHeight(&_block);
+	}
+	void operator()(assembly::FunctionDefinition const&)
+	{
+		solAssert(false, "Function definition not removed during desugaring phase.");
+	}
+
+private:
+	void generateAssignment(assembly::Identifier const& _variableName, SourceLocation const& _location)
+	{
+		auto var = m_scope.lookup(_variableName.name);
+		if (var)
+		{
+			Scope::Variable const& _var = boost::get<Scope::Variable>(*var);
+			if (int heightDiff = variableHeightDiff(_var, _location, true))
+				m_assembly.appendInstruction(solidity::swapInstruction(heightDiff - 1));
+			m_assembly.appendInstruction(solidity::Instruction::POP);
+		}
+		else
+		{
+			solAssert(
+				m_identifierAccess.generateCode,
+				"Identifier not found and no external access available."
+			);
+			m_identifierAccess.generateCode(_variableName, IdentifierContext::LValue, m_assembly);
+		}
+	}
+
+	/// Determines the stack height difference to the given variables. Automatically generates
+	/// errors if it is not yet in scope or the height difference is too large. Returns 0 on
+	/// errors and the (positive) stack height difference otherwise.
+	int variableHeightDiff(Scope::Variable const& _var, SourceLocation const& _location, bool _forSwap)
+	{
+		int heightDiff = m_assembly.stackHeight() - _var.stackHeight;
+		if (heightDiff <= (_forSwap ? 1 : 0) || heightDiff > (_forSwap ? 17 : 16))
+		{
+			//@TODO move this to analysis phase.
+			m_state.errors.push_back(make_shared<Error>(
+				Error::Type::TypeError,
+				"Variable inaccessible, too deep inside stack (" + boost::lexical_cast<string>(heightDiff) + ")",
+				_location
+			));
+			return 0;
+		}
+		else
+			return heightDiff;
+	}
+
+	void expectDeposit(int _deposit, int _oldHeight)
+	{
+		solAssert(m_assembly.stackHeight() == _oldHeight + _deposit, "Invalid stack deposit.");
+	}
+
+	void checkStackHeight(void const* _astElement)
+	{
+		solAssert(m_state.info.stackHeightInfo.count(_astElement), "Stack height for AST element not found.");
+		solAssert(
+			m_state.info.stackHeightInfo.at(_astElement) == m_assembly.stackHeight() - m_initialStackHeight,
+			"Stack height mismatch between analysis and code generation phase."
+		);
+	}
+
+	/// Assigns the label's id to a value taken from eth::Assembly if it has not yet been set.
+	void assignLabelIdIfUnset(Scope::Label& _label)
+	{
+		if (!_label.id)
+			_label.id.reset(m_assembly.newLabelId());
+	}
+
+
+	GeneratorState& m_state;
+	julia::AbstractAssembly& m_assembly;
+	Scope& m_scope;
+	ExternalIdentifierAccess m_identifierAccess;
+	int const m_initialStackHeight;
+};