diff options
Diffstat (limited to 'libyul')
| -rw-r--r-- | libyul/AsmAnalysis.cpp | 631 | ||||
| -rw-r--r-- | libyul/AsmAnalysis.h | 128 | ||||
| -rw-r--r-- | libyul/AsmAnalysisInfo.cpp | 26 | ||||
| -rw-r--r-- | libyul/AsmAnalysisInfo.h | 52 | ||||
| -rw-r--r-- | libyul/AsmCodeGen.cpp | 162 | ||||
| -rw-r--r-- | libyul/AsmCodeGen.h | 56 | ||||
| -rw-r--r-- | libyul/AsmData.h | 104 | ||||
| -rw-r--r-- | libyul/AsmDataForward.h | 65 | ||||
| -rw-r--r-- | libyul/AsmParser.cpp | 617 | ||||
| -rw-r--r-- | libyul/AsmParser.h | 95 | ||||
| -rw-r--r-- | libyul/AsmPrinter.cpp | 250 | ||||
| -rw-r--r-- | libyul/AsmPrinter.h | 68 | ||||
| -rw-r--r-- | libyul/AsmScope.cpp | 98 | ||||
| -rw-r--r-- | libyul/AsmScope.h | 105 | ||||
| -rw-r--r-- | libyul/AsmScopeFiller.cpp | 181 | ||||
| -rw-r--r-- | libyul/AsmScopeFiller.h | 88 |
16 files changed, 2726 insertions, 0 deletions
diff --git a/libyul/AsmAnalysis.cpp b/libyul/AsmAnalysis.cpp new file mode 100644 index 00000000..fb96f73c --- /dev/null +++ b/libyul/AsmAnalysis.cpp @@ -0,0 +1,631 @@ +/* + 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/>. +*/ +/** + * Analyzer part of inline assembly. + */ + +#include <libsolidity/inlineasm/AsmAnalysis.h> + +#include <libsolidity/inlineasm/AsmData.h> +#include <libsolidity/inlineasm/AsmScopeFiller.h> +#include <libsolidity/inlineasm/AsmScope.h> +#include <libsolidity/inlineasm/AsmAnalysisInfo.h> + +#include <liblangutil/ErrorReporter.h> + +#include <boost/range/adaptor/reversed.hpp> +#include <boost/algorithm/string.hpp> + +#include <memory> +#include <functional> + +using namespace std; +using namespace dev; +using namespace langutil; +using namespace dev::solidity; +using namespace dev::solidity::assembly; + +namespace { + +set<string> const builtinTypes{"bool", "u8", "s8", "u32", "s32", "u64", "s64", "u128", "s128", "u256", "s256"}; + +} + +bool AsmAnalyzer::analyze(Block const& _block) +{ + if (!(ScopeFiller(m_info, m_errorReporter))(_block)) + return false; + + return (*this)(_block); +} + +bool AsmAnalyzer::operator()(Label const& _label) +{ + solAssert(!_label.name.empty(), ""); + checkLooseFeature( + _label.location, + "The use of labels is disallowed. Please use \"if\", \"switch\", \"for\" or function calls instead." + ); + m_info.stackHeightInfo[&_label] = m_stackHeight; + warnOnInstructions(solidity::Instruction::JUMPDEST, _label.location); + return true; +} + +bool AsmAnalyzer::operator()(assembly::Instruction const& _instruction) +{ + checkLooseFeature( + _instruction.location, + "The use of non-functional instructions is disallowed. Please use functional notation instead." + ); + auto const& info = instructionInfo(_instruction.instruction); + m_stackHeight += info.ret - info.args; + m_info.stackHeightInfo[&_instruction] = m_stackHeight; + warnOnInstructions(_instruction.instruction, _instruction.location); + return true; +} + +bool AsmAnalyzer::operator()(assembly::Literal const& _literal) +{ + expectValidType(_literal.type.str(), _literal.location); + ++m_stackHeight; + if (_literal.kind == assembly::LiteralKind::String && _literal.value.str().size() > 32) + { + m_errorReporter.typeError( + _literal.location, + "String literal too long (" + to_string(_literal.value.str().size()) + " > 32)" + ); + return false; + } + else if (_literal.kind == assembly::LiteralKind::Number && bigint(_literal.value.str()) > u256(-1)) + { + m_errorReporter.typeError( + _literal.location, + "Number literal too large (> 256 bits)" + ); + return false; + } + else if (_literal.kind == assembly::LiteralKind::Boolean) + { + solAssert(m_flavour == AsmFlavour::Yul, ""); + solAssert(_literal.value == YulString{string("true")} || _literal.value == YulString{string("false")}, ""); + } + m_info.stackHeightInfo[&_literal] = m_stackHeight; + return true; +} + +bool AsmAnalyzer::operator()(assembly::Identifier const& _identifier) +{ + solAssert(!_identifier.name.empty(), ""); + size_t numErrorsBefore = m_errorReporter.errors().size(); + bool success = true; + if (m_currentScope->lookup(_identifier.name, Scope::Visitor( + [&](Scope::Variable const& _var) + { + if (!m_activeVariables.count(&_var)) + { + m_errorReporter.declarationError( + _identifier.location, + "Variable " + _identifier.name.str() + " used before it was declared." + ); + success = false; + } + ++m_stackHeight; + }, + [&](Scope::Label const&) + { + ++m_stackHeight; + }, + [&](Scope::Function const&) + { + m_errorReporter.typeError( + _identifier.location, + "Function " + _identifier.name.str() + " used without being called." + ); + success = false; + } + ))) + { + } + else + { + size_t stackSize(-1); + if (m_resolver) + { + bool insideFunction = m_currentScope->insideFunction(); + stackSize = m_resolver(_identifier, yul::IdentifierContext::RValue, insideFunction); + } + if (stackSize == size_t(-1)) + { + // Only add an error message if the callback did not do it. + if (numErrorsBefore == m_errorReporter.errors().size()) + m_errorReporter.declarationError(_identifier.location, "Identifier not found."); + success = false; + } + m_stackHeight += stackSize == size_t(-1) ? 1 : stackSize; + } + m_info.stackHeightInfo[&_identifier] = m_stackHeight; + return success; +} + +bool AsmAnalyzer::operator()(FunctionalInstruction const& _instr) +{ + solAssert(m_flavour != AsmFlavour::Yul, ""); + bool success = true; + for (auto const& arg: _instr.arguments | boost::adaptors::reversed) + if (!expectExpression(arg)) + success = false; + // Parser already checks that the number of arguments is correct. + auto const& info = instructionInfo(_instr.instruction); + solAssert(info.args == int(_instr.arguments.size()), ""); + m_stackHeight += info.ret - info.args; + m_info.stackHeightInfo[&_instr] = m_stackHeight; + warnOnInstructions(_instr.instruction, _instr.location); + return success; +} + +bool AsmAnalyzer::operator()(assembly::ExpressionStatement const& _statement) +{ + int initialStackHeight = m_stackHeight; + bool success = boost::apply_visitor(*this, _statement.expression); + if (m_stackHeight != initialStackHeight && (m_flavour != AsmFlavour::Loose || m_errorTypeForLoose)) + { + Error::Type errorType = m_flavour == AsmFlavour::Loose ? *m_errorTypeForLoose : Error::Type::TypeError; + string msg = + "Top-level expressions are not supposed to return values (this expression returns " + + to_string(m_stackHeight - initialStackHeight) + + " value" + + (m_stackHeight - initialStackHeight == 1 ? "" : "s") + + "). Use ``pop()`` or assign them."; + m_errorReporter.error(errorType, _statement.location, msg); + if (errorType != Error::Type::Warning) + success = false; + } + m_info.stackHeightInfo[&_statement] = m_stackHeight; + return success; +} + +bool AsmAnalyzer::operator()(assembly::StackAssignment const& _assignment) +{ + checkLooseFeature( + _assignment.location, + "The use of stack assignment is disallowed. Please use assignment in functional notation instead." + ); + bool success = checkAssignment(_assignment.variableName, size_t(-1)); + m_info.stackHeightInfo[&_assignment] = m_stackHeight; + return success; +} + +bool AsmAnalyzer::operator()(assembly::Assignment const& _assignment) +{ + solAssert(_assignment.value, ""); + int const expectedItems = _assignment.variableNames.size(); + solAssert(expectedItems >= 1, ""); + int const stackHeight = m_stackHeight; + bool success = boost::apply_visitor(*this, *_assignment.value); + if ((m_stackHeight - stackHeight) != expectedItems) + { + m_errorReporter.declarationError( + _assignment.location, + "Variable count does not match number of values (" + + to_string(expectedItems) + + " vs. " + + to_string(m_stackHeight - stackHeight) + + ")" + ); + return false; + } + for (auto const& variableName: _assignment.variableNames) + if (!checkAssignment(variableName, 1)) + success = false; + m_info.stackHeightInfo[&_assignment] = m_stackHeight; + return success; +} + +bool AsmAnalyzer::operator()(assembly::VariableDeclaration const& _varDecl) +{ + bool success = true; + int const numVariables = _varDecl.variables.size(); + if (_varDecl.value) + { + int const stackHeight = m_stackHeight; + success = boost::apply_visitor(*this, *_varDecl.value); + if ((m_stackHeight - stackHeight) != numVariables) + { + m_errorReporter.declarationError(_varDecl.location, "Variable count mismatch."); + return false; + } + } + else + m_stackHeight += numVariables; + + for (auto const& variable: _varDecl.variables) + { + expectValidType(variable.type.str(), variable.location); + m_activeVariables.insert(&boost::get<Scope::Variable>(m_currentScope->identifiers.at(variable.name))); + } + m_info.stackHeightInfo[&_varDecl] = m_stackHeight; + return success; +} + +bool AsmAnalyzer::operator()(assembly::FunctionDefinition const& _funDef) +{ + solAssert(!_funDef.name.empty(), ""); + Block const* virtualBlock = m_info.virtualBlocks.at(&_funDef).get(); + solAssert(virtualBlock, ""); + Scope& varScope = scope(virtualBlock); + for (auto const& var: _funDef.parameters + _funDef.returnVariables) + { + expectValidType(var.type.str(), var.location); + m_activeVariables.insert(&boost::get<Scope::Variable>(varScope.identifiers.at(var.name))); + } + + int const stackHeight = m_stackHeight; + m_stackHeight = _funDef.parameters.size() + _funDef.returnVariables.size(); + + bool success = (*this)(_funDef.body); + + m_stackHeight = stackHeight; + m_info.stackHeightInfo[&_funDef] = m_stackHeight; + return success; +} + +bool AsmAnalyzer::operator()(assembly::FunctionCall const& _funCall) +{ + solAssert(!_funCall.functionName.name.empty(), ""); + bool success = true; + size_t arguments = 0; + size_t returns = 0; + if (!m_currentScope->lookup(_funCall.functionName.name, Scope::Visitor( + [&](Scope::Variable const&) + { + m_errorReporter.typeError( + _funCall.functionName.location, + "Attempt to call variable instead of function." + ); + success = false; + }, + [&](Scope::Label const&) + { + m_errorReporter.typeError( + _funCall.functionName.location, + "Attempt to call label instead of function." + ); + success = false; + }, + [&](Scope::Function const& _fun) + { + /// TODO: compare types too + arguments = _fun.arguments.size(); + returns = _fun.returns.size(); + } + ))) + { + m_errorReporter.declarationError(_funCall.functionName.location, "Function not found."); + success = false; + } + if (success) + { + if (_funCall.arguments.size() != arguments) + { + m_errorReporter.typeError( + _funCall.functionName.location, + "Expected " + to_string(arguments) + " arguments but got " + + to_string(_funCall.arguments.size()) + "." + ); + success = false; + } + } + for (auto const& arg: _funCall.arguments | boost::adaptors::reversed) + if (!expectExpression(arg)) + success = false; + m_stackHeight += int(returns) - int(arguments); + m_info.stackHeightInfo[&_funCall] = m_stackHeight; + return success; +} + +bool AsmAnalyzer::operator()(If const& _if) +{ + bool success = true; + + if (!expectExpression(*_if.condition)) + success = false; + m_stackHeight--; + + if (!(*this)(_if.body)) + success = false; + + m_info.stackHeightInfo[&_if] = m_stackHeight; + + return success; +} + +bool AsmAnalyzer::operator()(Switch const& _switch) +{ + solAssert(_switch.expression, ""); + + bool success = true; + + if (!expectExpression(*_switch.expression)) + success = false; + + set<tuple<LiteralKind, YulString>> cases; + for (auto const& _case: _switch.cases) + { + if (_case.value) + { + int const initialStackHeight = m_stackHeight; + // We cannot use "expectExpression" here because *_case.value is not a + // Statement and would be converted to a Statement otherwise. + if (!(*this)(*_case.value)) + success = false; + expectDeposit(1, initialStackHeight, _case.value->location); + m_stackHeight--; + + /// Note: the parser ensures there is only one default case + auto val = make_tuple(_case.value->kind, _case.value->value); + if (!cases.insert(val).second) + { + m_errorReporter.declarationError( + _case.location, + "Duplicate case defined" + ); + success = false; + } + } + + if (!(*this)(_case.body)) + success = false; + } + + m_stackHeight--; + m_info.stackHeightInfo[&_switch] = m_stackHeight; + + return success; +} + +bool AsmAnalyzer::operator()(assembly::ForLoop const& _for) +{ + solAssert(_for.condition, ""); + + Scope* originalScope = m_currentScope; + + bool success = true; + if (!(*this)(_for.pre)) + success = false; + // The block was closed already, but we re-open it again and stuff the + // condition, the body and the post part inside. + m_stackHeight += scope(&_for.pre).numberOfVariables(); + m_currentScope = &scope(&_for.pre); + + if (!expectExpression(*_for.condition)) + success = false; + m_stackHeight--; + if (!(*this)(_for.body)) + success = false; + if (!(*this)(_for.post)) + success = false; + + m_stackHeight -= scope(&_for.pre).numberOfVariables(); + m_info.stackHeightInfo[&_for] = m_stackHeight; + m_currentScope = originalScope; + + return success; +} + +bool AsmAnalyzer::operator()(Block const& _block) +{ + bool success = true; + auto previousScope = m_currentScope; + m_currentScope = &scope(&_block); + + int const initialStackHeight = m_stackHeight; + + for (auto const& s: _block.statements) + if (!boost::apply_visitor(*this, s)) + success = false; + + m_stackHeight -= scope(&_block).numberOfVariables(); + + int const stackDiff = m_stackHeight - initialStackHeight; + if (stackDiff != 0) + { + m_errorReporter.declarationError( + _block.location, + "Unbalanced stack at the end of a block: " + + ( + stackDiff > 0 ? + to_string(stackDiff) + string(" surplus item(s).") : + to_string(-stackDiff) + string(" missing item(s).") + ) + ); + success = false; + } + + m_info.stackHeightInfo[&_block] = m_stackHeight; + m_currentScope = previousScope; + return success; +} + +bool AsmAnalyzer::expectExpression(Expression const& _expr) +{ + bool success = true; + int const initialHeight = m_stackHeight; + if (!boost::apply_visitor(*this, _expr)) + success = false; + if (!expectDeposit(1, initialHeight, locationOf(_expr))) + success = false; + return success; +} + +bool AsmAnalyzer::expectDeposit(int _deposit, int _oldHeight, SourceLocation const& _location) +{ + if (m_stackHeight - _oldHeight != _deposit) + { + m_errorReporter.typeError( + _location, + "Expected expression to return one item to the stack, but did return " + + to_string(m_stackHeight - _oldHeight) + + " items." + ); + return false; + } + return true; +} + +bool AsmAnalyzer::checkAssignment(assembly::Identifier const& _variable, size_t _valueSize) +{ + solAssert(!_variable.name.empty(), ""); + bool success = true; + size_t numErrorsBefore = m_errorReporter.errors().size(); + size_t variableSize(-1); + if (Scope::Identifier const* var = m_currentScope->lookup(_variable.name)) + { + // Check that it is a variable + if (var->type() != typeid(Scope::Variable)) + { + m_errorReporter.typeError(_variable.location, "Assignment requires variable."); + success = false; + } + else if (!m_activeVariables.count(&boost::get<Scope::Variable>(*var))) + { + m_errorReporter.declarationError( + _variable.location, + "Variable " + _variable.name.str() + " used before it was declared." + ); + success = false; + } + variableSize = 1; + } + else if (m_resolver) + { + bool insideFunction = m_currentScope->insideFunction(); + variableSize = m_resolver(_variable, yul::IdentifierContext::LValue, insideFunction); + } + if (variableSize == size_t(-1)) + { + // Only add message if the callback did not. + if (numErrorsBefore == m_errorReporter.errors().size()) + m_errorReporter.declarationError(_variable.location, "Variable not found or variable not lvalue."); + 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_errorReporter.typeError( + _variable.location, + "Variable size (" + + to_string(variableSize) + + ") and value size (" + + to_string(_valueSize) + + ") do not match." + ); + success = false; + } + return success; +} + +Scope& AsmAnalyzer::scope(Block const* _block) +{ + solAssert(m_info.scopes.count(_block) == 1, "Scope requested but not present."); + auto scopePtr = m_info.scopes.at(_block); + solAssert(scopePtr, "Scope requested but not present."); + return *scopePtr; +} +void AsmAnalyzer::expectValidType(string const& type, SourceLocation const& _location) +{ + if (m_flavour != AsmFlavour::Yul) + return; + + if (!builtinTypes.count(type)) + m_errorReporter.typeError( + _location, + "\"" + type + "\" is not a valid type (user defined types are not yet supported)." + ); +} + +void AsmAnalyzer::warnOnInstructions(solidity::Instruction _instr, SourceLocation const& _location) +{ + // We assume that returndatacopy, returndatasize and staticcall are either all available + // or all not available. + solAssert(m_evmVersion.supportsReturndata() == m_evmVersion.hasStaticCall(), ""); + // Similarly we assume bitwise shifting and create2 go together. + solAssert(m_evmVersion.hasBitwiseShifting() == m_evmVersion.hasCreate2(), ""); + + if (_instr == solidity::Instruction::EXTCODEHASH) + m_errorReporter.warning( + _location, + "The \"" + + boost::to_lower_copy(instructionInfo(_instr).name) + + "\" instruction is not supported by the VM version \"" + + "" + m_evmVersion.name() + + "\" you are currently compiling for. " + + "It will be interpreted as an invalid instruction on this VM." + ); + else if (( + _instr == solidity::Instruction::RETURNDATACOPY || + _instr == solidity::Instruction::RETURNDATASIZE || + _instr == solidity::Instruction::STATICCALL + ) && !m_evmVersion.supportsReturndata()) + m_errorReporter.warning( + _location, + "The \"" + + boost::to_lower_copy(instructionInfo(_instr).name) + + "\" instruction is only available for Byzantium-compatible VMs. " + + "You are currently compiling for \"" + + m_evmVersion.name() + + "\", where it will be interpreted as an invalid instruction." + ); + else if (( + _instr == solidity::Instruction::SHL || + _instr == solidity::Instruction::SHR || + _instr == solidity::Instruction::SAR || + _instr == solidity::Instruction::CREATE2 + ) && !m_evmVersion.hasBitwiseShifting()) + m_errorReporter.warning( + _location, + "The \"" + + boost::to_lower_copy(instructionInfo(_instr).name) + + "\" instruction is only available for Constantinople-compatible VMs. " + + "You are currently compiling for \"" + + m_evmVersion.name() + + "\", where it will be interpreted as an invalid instruction." + ); + + if (_instr == solidity::Instruction::JUMP || _instr == solidity::Instruction::JUMPI || _instr == solidity::Instruction::JUMPDEST) + { + solAssert(m_flavour == AsmFlavour::Loose, ""); + m_errorReporter.error( + m_errorTypeForLoose ? *m_errorTypeForLoose : Error::Type::Warning, + _location, + "Jump instructions and labels are low-level EVM features that can lead to " + "incorrect stack access. Because of that they are discouraged. " + "Please consider using \"switch\", \"if\" or \"for\" statements instead." + ); + } +} + +void AsmAnalyzer::checkLooseFeature(SourceLocation const& _location, string const& _description) +{ + if (m_flavour != AsmFlavour::Loose) + solAssert(false, _description); + else if (m_errorTypeForLoose) + m_errorReporter.error(*m_errorTypeForLoose, _location, _description); +} diff --git a/libyul/AsmAnalysis.h b/libyul/AsmAnalysis.h new file mode 100644 index 00000000..194f736e --- /dev/null +++ b/libyul/AsmAnalysis.h @@ -0,0 +1,128 @@ +/* + 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/>. +*/ +/** + * Analysis part of inline assembly. + */ + +#pragma once + +#include <liblangutil/Exceptions.h> +#include <liblangutil/EVMVersion.h> + +#include <libsolidity/inlineasm/AsmScope.h> + +#include <libyul/backends/evm/AbstractAssembly.h> + +#include <libsolidity/inlineasm/AsmDataForward.h> + +#include <boost/variant.hpp> +#include <boost/optional.hpp> + +#include <functional> +#include <memory> + +namespace langutil +{ +class ErrorReporter; +struct SourceLocation; +} + +namespace dev +{ +namespace solidity +{ +namespace assembly +{ + +struct AsmAnalysisInfo; + +/** + * Performs the full analysis stage, calls the ScopeFiller internally, then resolves + * references and performs other checks. + * If all these checks pass, code generation should not throw errors. + */ +class AsmAnalyzer: public boost::static_visitor<bool> +{ +public: + explicit AsmAnalyzer( + AsmAnalysisInfo& _analysisInfo, + langutil::ErrorReporter& _errorReporter, + EVMVersion _evmVersion, + boost::optional<langutil::Error::Type> _errorTypeForLoose, + AsmFlavour _flavour = AsmFlavour::Loose, + yul::ExternalIdentifierAccess::Resolver const& _resolver = yul::ExternalIdentifierAccess::Resolver() + ): + m_resolver(_resolver), + m_info(_analysisInfo), + m_errorReporter(_errorReporter), + m_evmVersion(_evmVersion), + m_flavour(_flavour), + m_errorTypeForLoose(_errorTypeForLoose) + {} + + bool analyze(assembly::Block const& _block); + + bool operator()(assembly::Instruction const&); + bool operator()(assembly::Literal const& _literal); + bool operator()(assembly::Identifier const&); + bool operator()(assembly::FunctionalInstruction const& _functionalInstruction); + bool operator()(assembly::Label const& _label); + bool operator()(assembly::ExpressionStatement const&); + bool operator()(assembly::StackAssignment const&); + bool operator()(assembly::Assignment const& _assignment); + bool operator()(assembly::VariableDeclaration const& _variableDeclaration); + bool operator()(assembly::FunctionDefinition const& _functionDefinition); + bool operator()(assembly::FunctionCall const& _functionCall); + bool operator()(assembly::If const& _if); + bool operator()(assembly::Switch const& _switch); + bool operator()(assembly::ForLoop const& _forLoop); + bool operator()(assembly::Block const& _block); + +private: + /// Visits the statement and expects it to deposit one item onto the stack. + bool expectExpression(Expression const& _expr); + bool expectDeposit(int _deposit, int _oldHeight, langutil::SourceLocation const& _location); + + /// 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)); + + Scope& scope(assembly::Block const* _block); + void expectValidType(std::string const& type, langutil::SourceLocation const& _location); + void warnOnInstructions(solidity::Instruction _instr, langutil::SourceLocation const& _location); + + /// Depending on @a m_flavour and @a m_errorTypeForLoose, throws an internal compiler + /// exception (if the flavour is not Loose), reports an error/warning + /// (if m_errorTypeForLoose is set) or does nothing. + void checkLooseFeature(langutil::SourceLocation const& _location, std::string const& _description); + + int m_stackHeight = 0; + yul::ExternalIdentifierAccess::Resolver m_resolver; + Scope* m_currentScope = nullptr; + /// Variables that are active at the current point in assembly (as opposed to + /// "part of the scope but not yet declared") + std::set<Scope::Variable const*> m_activeVariables; + AsmAnalysisInfo& m_info; + langutil::ErrorReporter& m_errorReporter; + EVMVersion m_evmVersion; + AsmFlavour m_flavour = AsmFlavour::Loose; + boost::optional<langutil::Error::Type> m_errorTypeForLoose; +}; + +} +} +} diff --git a/libyul/AsmAnalysisInfo.cpp b/libyul/AsmAnalysisInfo.cpp new file mode 100644 index 00000000..22318b12 --- /dev/null +++ b/libyul/AsmAnalysisInfo.cpp @@ -0,0 +1,26 @@ +/* + 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/>. +*/ +/** + * Information generated during analyzer part of inline assembly. + */ + +#include <libsolidity/inlineasm/AsmAnalysisInfo.h> + +#include <libsolidity/inlineasm/AsmScope.h> + +#include <ostream> + diff --git a/libyul/AsmAnalysisInfo.h b/libyul/AsmAnalysisInfo.h new file mode 100644 index 00000000..bd3b28c4 --- /dev/null +++ b/libyul/AsmAnalysisInfo.h @@ -0,0 +1,52 @@ +/* + 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/>. +*/ +/** + * Information generated during analyzer part of inline assembly. + */ + +#pragma once + +#include <libsolidity/inlineasm/AsmDataForward.h> + +#include <boost/variant.hpp> + +#include <map> +#include <memory> +#include <vector> + +namespace dev +{ +namespace solidity +{ +namespace assembly +{ + +struct Scope; + +struct AsmAnalysisInfo +{ + using StackHeightInfo = std::map<void const*, int>; + using Scopes = std::map<assembly::Block const*, std::shared_ptr<Scope>>; + Scopes scopes; + StackHeightInfo stackHeightInfo; + /// Virtual blocks which will be used for scopes for function arguments and return values. + std::map<FunctionDefinition const*, std::shared_ptr<assembly::Block const>> virtualBlocks; +}; + +} +} +} diff --git a/libyul/AsmCodeGen.cpp b/libyul/AsmCodeGen.cpp new file mode 100644 index 00000000..2800cc7b --- /dev/null +++ b/libyul/AsmCodeGen.cpp @@ -0,0 +1,162 @@ +/* + 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/>. +*/ +/** + * @author Christian <c@ethdev.com> + * @date 2016 + * Code-generating part of inline assembly. + */ + +#include <libsolidity/inlineasm/AsmCodeGen.h> + +#include <libsolidity/inlineasm/AsmParser.h> +#include <libsolidity/inlineasm/AsmData.h> +#include <libsolidity/inlineasm/AsmScope.h> +#include <libsolidity/inlineasm/AsmAnalysis.h> +#include <libsolidity/inlineasm/AsmAnalysisInfo.h> + +#include <libevmasm/Assembly.h> +#include <liblangutil/SourceLocation.h> +#include <libevmasm/Instruction.h> + +#include <libyul/backends/evm/AbstractAssembly.h> +#include <libyul/backends/evm/EVMCodeTransform.h> + +#include <libdevcore/CommonIO.h> + +#include <boost/range/adaptor/reversed.hpp> +#include <boost/range/adaptor/map.hpp> +#include <boost/range/algorithm/count_if.hpp> + +#include <memory> +#include <functional> + +using namespace std; +using namespace dev; +using namespace langutil; +using namespace dev::solidity; +using namespace dev::solidity::assembly; + +class EthAssemblyAdapter: public yul::AbstractAssembly +{ +public: + explicit EthAssemblyAdapter(eth::Assembly& _assembly): + m_assembly(_assembly) + { + } + virtual void setSourceLocation(SourceLocation const& _location) override + { + m_assembly.setSourceLocation(_location); + } + virtual int stackHeight() const override { return m_assembly.deposit(); } + virtual void appendInstruction(solidity::Instruction _instruction) override + { + m_assembly.append(_instruction); + } + virtual void appendConstant(u256 const& _constant) override + { + m_assembly.append(_constant); + } + /// Append a label. + virtual void appendLabel(LabelID _labelId) override + { + m_assembly.append(eth::AssemblyItem(eth::Tag, _labelId)); + } + /// Append a label reference. + virtual void appendLabelReference(LabelID _labelId) override + { + m_assembly.append(eth::AssemblyItem(eth::PushTag, _labelId)); + } + virtual size_t newLabelId() override + { + return assemblyTagToIdentifier(m_assembly.newTag()); + } + virtual size_t namedLabel(std::string const& _name) override + { + return assemblyTagToIdentifier(m_assembly.namedTag(_name)); + } + virtual void appendLinkerSymbol(std::string const& _linkerSymbol) override + { + m_assembly.appendLibraryAddress(_linkerSymbol); + } + virtual void appendJump(int _stackDiffAfter) override + { + appendInstruction(solidity::Instruction::JUMP); + m_assembly.adjustDeposit(_stackDiffAfter); + } + virtual void appendJumpTo(LabelID _labelId, int _stackDiffAfter) override + { + appendLabelReference(_labelId); + appendJump(_stackDiffAfter); + } + virtual void appendJumpToIf(LabelID _labelId) override + { + appendLabelReference(_labelId); + appendInstruction(solidity::Instruction::JUMPI); + } + virtual void appendBeginsub(LabelID, int) override + { + // TODO we could emulate that, though + solAssert(false, "BEGINSUB not implemented for EVM 1.0"); + } + /// Call a subroutine. + virtual void appendJumpsub(LabelID, int, int) override + { + // TODO we could emulate that, though + solAssert(false, "JUMPSUB not implemented for EVM 1.0"); + } + + /// Return from a subroutine. + virtual void appendReturnsub(int, int) override + { + // TODO we could emulate that, though + solAssert(false, "RETURNSUB not implemented for EVM 1.0"); + } + + virtual void appendAssemblySize() override + { + m_assembly.appendProgramSize(); + } + +private: + static LabelID assemblyTagToIdentifier(eth::AssemblyItem const& _tag) + { + u256 id = _tag.data(); + solAssert(id <= std::numeric_limits<LabelID>::max(), "Tag id too large."); + return LabelID(id); + } + + eth::Assembly& m_assembly; +}; + +void assembly::CodeGenerator::assemble( + Block const& _parsedData, + AsmAnalysisInfo& _analysisInfo, + eth::Assembly& _assembly, + yul::ExternalIdentifierAccess const& _identifierAccess, + bool _useNamedLabelsForFunctions +) +{ + EthAssemblyAdapter assemblyAdapter(_assembly); + yul::CodeTransform( + assemblyAdapter, + _analysisInfo, + false, + false, + _identifierAccess, + _useNamedLabelsForFunctions + )(_parsedData); +} diff --git a/libyul/AsmCodeGen.h b/libyul/AsmCodeGen.h new file mode 100644 index 00000000..bbc31397 --- /dev/null +++ b/libyul/AsmCodeGen.h @@ -0,0 +1,56 @@ +/* + 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/>. +*/ +/** + * @author Christian <c@ethdev.com> + * @date 2016 + * Code-generating part of inline assembly. + */ + +#pragma once + +#include <libsolidity/inlineasm/AsmAnalysis.h> + +#include <functional> + +namespace dev +{ +namespace eth +{ +class Assembly; +} +namespace solidity +{ +namespace assembly +{ +struct Block; + +class CodeGenerator +{ +public: + /// Performs code generation and appends generated to _assembly. + static void assemble( + Block const& _parsedData, + AsmAnalysisInfo& _analysisInfo, + eth::Assembly& _assembly, + yul::ExternalIdentifierAccess const& _identifierAccess = yul::ExternalIdentifierAccess(), + bool _useNamedLabelsForFunctions = false + ); +}; + +} +} +} diff --git a/libyul/AsmData.h b/libyul/AsmData.h new file mode 100644 index 00000000..23a9db75 --- /dev/null +++ b/libyul/AsmData.h @@ -0,0 +1,104 @@ +/* + 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/>. +*/ +/** + * @author Christian <c@ethdev.com> + * @date 2016 + * Parsed inline assembly to be used by the AST + */ + +#pragma once + +#include <libsolidity/inlineasm/AsmDataForward.h> + +#include <libevmasm/Instruction.h> +#include <liblangutil/SourceLocation.h> + +#include <libyul/YulString.h> + +#include <boost/variant.hpp> +#include <boost/noncopyable.hpp> + +#include <map> +#include <memory> + +namespace dev +{ +namespace solidity +{ +namespace assembly +{ + +using YulString = dev::yul::YulString; +using Type = YulString; + +struct TypedName { langutil::SourceLocation location; YulString name; Type type; }; +using TypedNameList = std::vector<TypedName>; + +/// Direct EVM instruction (except PUSHi and JUMPDEST) +struct Instruction { langutil::SourceLocation location; solidity::Instruction instruction; }; +/// Literal number or string (up to 32 bytes) +enum class LiteralKind { Number, Boolean, String }; +struct Literal { langutil::SourceLocation location; LiteralKind kind; YulString value; Type type; }; +/// External / internal identifier or label reference +struct Identifier { langutil::SourceLocation location; YulString name; }; +/// Jump label ("name:") +struct Label { langutil::SourceLocation location; YulString name; }; +/// Assignment from stack (":= x", moves stack top into x, potentially multiple slots) +struct StackAssignment { langutil::SourceLocation location; Identifier variableName; }; +/// Assignment ("x := mload(20:u256)", expects push-1-expression on the right hand +/// side and requires x to occupy exactly one stack slot. +/// +/// Multiple assignment ("x, y := f()"), where the left hand side variables each occupy +/// a single stack slot and expects a single expression on the right hand returning +/// the same amount of items as the number of variables. +struct Assignment { langutil::SourceLocation location; std::vector<Identifier> variableNames; std::shared_ptr<Expression> value; }; +/// Functional instruction, e.g. "mul(mload(20:u256), add(2:u256, x))" +struct FunctionalInstruction { langutil::SourceLocation location; solidity::Instruction instruction; std::vector<Expression> arguments; }; +struct FunctionCall { langutil::SourceLocation location; Identifier functionName; std::vector<Expression> arguments; }; +/// Statement that contains only a single expression +struct ExpressionStatement { langutil::SourceLocation location; Expression expression; }; +/// Block-scope variable declaration ("let x:u256 := mload(20:u256)"), non-hoisted +struct VariableDeclaration { langutil::SourceLocation location; TypedNameList variables; std::shared_ptr<Expression> value; }; +/// Block that creates a scope (frees declared stack variables) +struct Block { langutil::SourceLocation location; std::vector<Statement> statements; }; +/// Function definition ("function f(a, b) -> (d, e) { ... }") +struct FunctionDefinition { langutil::SourceLocation location; YulString name; TypedNameList parameters; TypedNameList returnVariables; Block body; }; +/// Conditional execution without "else" part. +struct If { langutil::SourceLocation location; std::shared_ptr<Expression> condition; Block body; }; +/// Switch case or default case +struct Case { langutil::SourceLocation location; std::shared_ptr<Literal> value; Block body; }; +/// Switch statement +struct Switch { langutil::SourceLocation location; std::shared_ptr<Expression> expression; std::vector<Case> cases; }; +struct ForLoop { langutil::SourceLocation location; Block pre; std::shared_ptr<Expression> condition; Block post; Block body; }; + +struct LocationExtractor: boost::static_visitor<langutil::SourceLocation> +{ + template <class T> langutil::SourceLocation operator()(T const& _node) const + { + return _node.location; + } +}; + +/// Extracts the source location from an inline assembly node. +template <class T> inline langutil::SourceLocation locationOf(T const& _node) +{ + return boost::apply_visitor(LocationExtractor(), _node); +} + +} +} +} diff --git a/libyul/AsmDataForward.h b/libyul/AsmDataForward.h new file mode 100644 index 00000000..69cf8f1d --- /dev/null +++ b/libyul/AsmDataForward.h @@ -0,0 +1,65 @@ +/* + 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/>. +*/ +/** + * @author Christian <c@ethdev.com> + * @date 2016 + * Forward declaration of classes for inline assembly / Yul AST + */ + +#pragma once + +#include <boost/variant.hpp> + +namespace dev +{ +namespace solidity +{ +namespace assembly +{ + +struct Instruction; +struct Literal; +struct Label; +struct StackAssignment; +struct Identifier; +struct Assignment; +struct VariableDeclaration; +struct FunctionalInstruction; +struct FunctionDefinition; +struct FunctionCall; +struct If; +struct Switch; +struct Case; +struct ForLoop; +struct ExpressionStatement; +struct Block; + +struct TypedName; + +using Expression = boost::variant<FunctionalInstruction, FunctionCall, Identifier, Literal>; +using Statement = boost::variant<ExpressionStatement, Instruction, Label, StackAssignment, Assignment, VariableDeclaration, FunctionDefinition, If, Switch, ForLoop, Block>; + +enum class AsmFlavour +{ + Loose, // no types, EVM instructions as function, jumps and direct stack manipulations + Strict, // no types, EVM instructions as functions, but no jumps and no direct stack manipulations + Yul // same as Strict mode with types +}; + +} +} +} diff --git a/libyul/AsmParser.cpp b/libyul/AsmParser.cpp new file mode 100644 index 00000000..b11f70e0 --- /dev/null +++ b/libyul/AsmParser.cpp @@ -0,0 +1,617 @@ +/* + 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/>. +*/ +/** + * @author Christian <c@ethdev.com> + * @date 2016 + * Solidity inline assembly parser. + */ + +#include <libsolidity/inlineasm/AsmParser.h> +#include <liblangutil/Scanner.h> +#include <liblangutil/ErrorReporter.h> + +#include <boost/algorithm/string.hpp> + +#include <cctype> +#include <algorithm> + +using namespace std; +using namespace dev; +using namespace langutil; +using namespace dev::solidity; +using namespace dev::solidity::assembly; + +shared_ptr<assembly::Block> Parser::parse(std::shared_ptr<Scanner> const& _scanner, bool _reuseScanner) +{ + m_recursionDepth = 0; + try + { + m_scanner = _scanner; + auto block = make_shared<Block>(parseBlock()); + if (!_reuseScanner) + expectToken(Token::EOS); + return block; + } + catch (FatalError const&) + { + if (m_errorReporter.errors().empty()) + throw; // Something is weird here, rather throw again. + } + return nullptr; +} + +assembly::Block Parser::parseBlock() +{ + RecursionGuard recursionGuard(*this); + assembly::Block block = createWithLocation<Block>(); + expectToken(Token::LBrace); + while (currentToken() != Token::RBrace) + block.statements.emplace_back(parseStatement()); + block.location.end = endPosition(); + advance(); + return block; +} + +assembly::Statement Parser::parseStatement() +{ + RecursionGuard recursionGuard(*this); + switch (currentToken()) + { + case Token::Let: + return parseVariableDeclaration(); + case Token::Function: + return parseFunctionDefinition(); + case Token::LBrace: + return parseBlock(); + case Token::If: + { + assembly::If _if = createWithLocation<assembly::If>(); + m_scanner->next(); + _if.condition = make_shared<Expression>(parseExpression()); + _if.body = parseBlock(); + return _if; + } + case Token::Switch: + { + assembly::Switch _switch = createWithLocation<assembly::Switch>(); + m_scanner->next(); + _switch.expression = make_shared<Expression>(parseExpression()); + while (m_scanner->currentToken() == Token::Case) + _switch.cases.emplace_back(parseCase()); + if (m_scanner->currentToken() == Token::Default) + _switch.cases.emplace_back(parseCase()); + if (m_scanner->currentToken() == Token::Default) + fatalParserError("Only one default case allowed."); + else if (m_scanner->currentToken() == Token::Case) + fatalParserError("Case not allowed after default case."); + if (_switch.cases.empty()) + fatalParserError("Switch statement without any cases."); + _switch.location.end = _switch.cases.back().body.location.end; + return _switch; + } + case Token::For: + return parseForLoop(); + case Token::Assign: + { + if (m_flavour != AsmFlavour::Loose) + break; + assembly::StackAssignment assignment = createWithLocation<assembly::StackAssignment>(); + advance(); + expectToken(Token::Colon); + assignment.variableName.location = location(); + assignment.variableName.name = YulString(currentLiteral()); + if (instructions().count(assignment.variableName.name.str())) + fatalParserError("Identifier expected, got instruction name."); + assignment.location.end = endPosition(); + expectToken(Token::Identifier); + return assignment; + } + default: + break; + } + // Options left: + // Simple instruction (might turn into functional), + // literal, + // identifier (might turn into label or functional assignment) + ElementaryOperation elementary(parseElementaryOperation()); + switch (currentToken()) + { + case Token::LParen: + { + Expression expr = parseCall(std::move(elementary)); + return ExpressionStatement{locationOf(expr), expr}; + } + case Token::Comma: + { + // if a comma follows, a multiple assignment is assumed + + if (elementary.type() != typeid(assembly::Identifier)) + fatalParserError("Label name / variable name must precede \",\" (multiple assignment)."); + assembly::Identifier const& identifier = boost::get<assembly::Identifier>(elementary); + + Assignment assignment = createWithLocation<Assignment>(identifier.location); + assignment.variableNames.emplace_back(identifier); + + do + { + expectToken(Token::Comma); + elementary = parseElementaryOperation(); + if (elementary.type() != typeid(assembly::Identifier)) + fatalParserError("Variable name expected in multiple assignment."); + assignment.variableNames.emplace_back(boost::get<assembly::Identifier>(elementary)); + } + while (currentToken() == Token::Comma); + + expectToken(Token::Colon); + expectToken(Token::Assign); + + assignment.value.reset(new Expression(parseExpression())); + assignment.location.end = locationOf(*assignment.value).end; + return assignment; + } + case Token::Colon: + { + if (elementary.type() != typeid(assembly::Identifier)) + fatalParserError("Label name / variable name must precede \":\"."); + assembly::Identifier const& identifier = boost::get<assembly::Identifier>(elementary); + advance(); + // identifier:=: should be parsed as identifier: =: (i.e. a label), + // while identifier:= (being followed by a non-colon) as identifier := (assignment). + if (currentToken() == Token::Assign && peekNextToken() != Token::Colon) + { + assembly::Assignment assignment = createWithLocation<assembly::Assignment>(identifier.location); + if (m_flavour != AsmFlavour::Yul && instructions().count(identifier.name.str())) + fatalParserError("Cannot use instruction names for identifier names."); + advance(); + assignment.variableNames.emplace_back(identifier); + assignment.value.reset(new Expression(parseExpression())); + assignment.location.end = locationOf(*assignment.value).end; + return assignment; + } + else + { + // label + if (m_flavour != AsmFlavour::Loose) + fatalParserError("Labels are not supported."); + Label label = createWithLocation<Label>(identifier.location); + label.name = identifier.name; + return label; + } + } + default: + if (m_flavour != AsmFlavour::Loose) + fatalParserError("Call or assignment expected."); + break; + } + if (elementary.type() == typeid(assembly::Identifier)) + { + Expression expr = boost::get<assembly::Identifier>(elementary); + return ExpressionStatement{locationOf(expr), expr}; + } + else if (elementary.type() == typeid(assembly::Literal)) + { + Expression expr = boost::get<assembly::Literal>(elementary); + return ExpressionStatement{locationOf(expr), expr}; + } + else + { + solAssert(elementary.type() == typeid(assembly::Instruction), "Invalid elementary operation."); + return boost::get<assembly::Instruction>(elementary); + } +} + +assembly::Case Parser::parseCase() +{ + RecursionGuard recursionGuard(*this); + assembly::Case _case = createWithLocation<assembly::Case>(); + if (m_scanner->currentToken() == Token::Default) + m_scanner->next(); + else if (m_scanner->currentToken() == Token::Case) + { + m_scanner->next(); + ElementaryOperation literal = parseElementaryOperation(); + if (literal.type() != typeid(assembly::Literal)) + fatalParserError("Literal expected."); + _case.value = make_shared<Literal>(boost::get<assembly::Literal>(std::move(literal))); + } + else + fatalParserError("Case or default case expected."); + _case.body = parseBlock(); + _case.location.end = _case.body.location.end; + return _case; +} + +assembly::ForLoop Parser::parseForLoop() +{ + RecursionGuard recursionGuard(*this); + ForLoop forLoop = createWithLocation<ForLoop>(); + expectToken(Token::For); + forLoop.pre = parseBlock(); + forLoop.condition = make_shared<Expression>(parseExpression()); + forLoop.post = parseBlock(); + forLoop.body = parseBlock(); + forLoop.location.end = forLoop.body.location.end; + return forLoop; +} + +assembly::Expression Parser::parseExpression() +{ + RecursionGuard recursionGuard(*this); + // In strict mode, this might parse a plain Instruction, but + // it will be converted to a FunctionalInstruction inside + // parseCall below. + ElementaryOperation operation = parseElementaryOperation(); + if (operation.type() == typeid(Instruction)) + { + Instruction const& instr = boost::get<Instruction>(operation); + // Disallow instructions returning multiple values (and DUP/SWAP) as expression. + if ( + instructionInfo(instr.instruction).ret != 1 || + isDupInstruction(instr.instruction) || + isSwapInstruction(instr.instruction) + ) + fatalParserError( + "Instruction \"" + + instructionNames().at(instr.instruction) + + "\" not allowed in this context." + ); + if (m_flavour != AsmFlavour::Loose && currentToken() != Token::LParen) + fatalParserError( + "Non-functional instructions are not allowed in this context." + ); + // Enforce functional notation for instructions requiring multiple arguments. + int args = instructionInfo(instr.instruction).args; + if (args > 0 && currentToken() != Token::LParen) + fatalParserError(string( + "Expected '(' (instruction \"" + + instructionNames().at(instr.instruction) + + "\" expects " + + to_string(args) + + " arguments)" + )); + } + if (currentToken() == Token::LParen) + return parseCall(std::move(operation)); + else if (operation.type() == typeid(Instruction)) + { + // Instructions not taking arguments are allowed as expressions. + solAssert(m_flavour == AsmFlavour::Loose, ""); + Instruction& instr = boost::get<Instruction>(operation); + return FunctionalInstruction{std::move(instr.location), instr.instruction, {}}; + } + else if (operation.type() == typeid(assembly::Identifier)) + return boost::get<assembly::Identifier>(operation); + else + { + solAssert(operation.type() == typeid(assembly::Literal), ""); + return boost::get<assembly::Literal>(operation); + } +} + +std::map<string, dev::solidity::Instruction> const& Parser::instructions() +{ + // Allowed instructions, lowercase names. + static map<string, dev::solidity::Instruction> s_instructions; + if (s_instructions.empty()) + { + for (auto const& instruction: solidity::c_instructions) + { + if ( + instruction.second == solidity::Instruction::JUMPDEST || + solidity::isPushInstruction(instruction.second) + ) + continue; + string name = instruction.first; + transform(name.begin(), name.end(), name.begin(), [](unsigned char _c) { return tolower(_c); }); + s_instructions[name] = instruction.second; + } + } + return s_instructions; +} + +std::map<dev::solidity::Instruction, string> const& Parser::instructionNames() +{ + static map<dev::solidity::Instruction, string> s_instructionNames; + if (s_instructionNames.empty()) + { + for (auto const& instr: instructions()) + s_instructionNames[instr.second] = instr.first; + // set the ambiguous instructions to a clear default + s_instructionNames[solidity::Instruction::SELFDESTRUCT] = "selfdestruct"; + s_instructionNames[solidity::Instruction::KECCAK256] = "keccak256"; + } + return s_instructionNames; +} + +Parser::ElementaryOperation Parser::parseElementaryOperation() +{ + RecursionGuard recursionGuard(*this); + ElementaryOperation ret; + switch (currentToken()) + { + case Token::Identifier: + case Token::Return: + case Token::Byte: + case Token::Address: + { + string literal; + if (currentToken() == Token::Return) + literal = "return"; + else if (currentToken() == Token::Byte) + literal = "byte"; + else if (currentToken() == Token::Address) + literal = "address"; + else + literal = currentLiteral(); + // first search the set of instructions. + if (m_flavour != AsmFlavour::Yul && instructions().count(literal)) + { + dev::solidity::Instruction const& instr = instructions().at(literal); + ret = Instruction{location(), instr}; + } + else + ret = Identifier{location(), YulString{literal}}; + advance(); + break; + } + case Token::StringLiteral: + case Token::Number: + case Token::TrueLiteral: + case Token::FalseLiteral: + { + LiteralKind kind = LiteralKind::Number; + switch (currentToken()) + { + case Token::StringLiteral: + kind = LiteralKind::String; + break; + case Token::Number: + if (!isValidNumberLiteral(currentLiteral())) + fatalParserError("Invalid number literal."); + kind = LiteralKind::Number; + break; + case Token::TrueLiteral: + case Token::FalseLiteral: + kind = LiteralKind::Boolean; + break; + default: + break; + } + + Literal literal{ + location(), + kind, + YulString{currentLiteral()}, + {} + }; + advance(); + if (m_flavour == AsmFlavour::Yul) + { + expectToken(Token::Colon); + literal.location.end = endPosition(); + literal.type = YulString{expectAsmIdentifier()}; + } + else if (kind == LiteralKind::Boolean) + fatalParserError("True and false are not valid literals."); + ret = std::move(literal); + break; + } + default: + fatalParserError( + m_flavour == AsmFlavour::Yul ? + "Literal or identifier expected." : + "Literal, identifier or instruction expected." + ); + } + return ret; +} + +assembly::VariableDeclaration Parser::parseVariableDeclaration() +{ + RecursionGuard recursionGuard(*this); + VariableDeclaration varDecl = createWithLocation<VariableDeclaration>(); + expectToken(Token::Let); + while (true) + { + varDecl.variables.emplace_back(parseTypedName()); + if (currentToken() == Token::Comma) + expectToken(Token::Comma); + else + break; + } + if (currentToken() == Token::Colon) + { + expectToken(Token::Colon); + expectToken(Token::Assign); + varDecl.value.reset(new Expression(parseExpression())); + varDecl.location.end = locationOf(*varDecl.value).end; + } + else + varDecl.location.end = varDecl.variables.back().location.end; + return varDecl; +} + +assembly::FunctionDefinition Parser::parseFunctionDefinition() +{ + RecursionGuard recursionGuard(*this); + FunctionDefinition funDef = createWithLocation<FunctionDefinition>(); + expectToken(Token::Function); + funDef.name = YulString{expectAsmIdentifier()}; + expectToken(Token::LParen); + while (currentToken() != Token::RParen) + { + funDef.parameters.emplace_back(parseTypedName()); + if (currentToken() == Token::RParen) + break; + expectToken(Token::Comma); + } + expectToken(Token::RParen); + if (currentToken() == Token::Sub) + { + expectToken(Token::Sub); + expectToken(Token::GreaterThan); + while (true) + { + funDef.returnVariables.emplace_back(parseTypedName()); + if (currentToken() == Token::LBrace) + break; + expectToken(Token::Comma); + } + } + funDef.body = parseBlock(); + funDef.location.end = funDef.body.location.end; + return funDef; +} + +assembly::Expression Parser::parseCall(Parser::ElementaryOperation&& _initialOp) +{ + RecursionGuard recursionGuard(*this); + if (_initialOp.type() == typeid(Instruction)) + { + solAssert(m_flavour != AsmFlavour::Yul, "Instructions are invalid in Yul"); + Instruction& instruction = boost::get<Instruction>(_initialOp); + FunctionalInstruction ret; + ret.instruction = instruction.instruction; + ret.location = std::move(instruction.location); + solidity::Instruction instr = ret.instruction; + InstructionInfo instrInfo = instructionInfo(instr); + if (solidity::isDupInstruction(instr)) + fatalParserError("DUPi instructions not allowed for functional notation"); + if (solidity::isSwapInstruction(instr)) + fatalParserError("SWAPi instructions not allowed for functional notation"); + expectToken(Token::LParen); + unsigned args = unsigned(instrInfo.args); + for (unsigned i = 0; i < args; ++i) + { + /// check for premature closing parentheses + if (currentToken() == Token::RParen) + fatalParserError(string( + "Expected expression (instruction \"" + + instructionNames().at(instr) + + "\" expects " + + to_string(args) + + " arguments)" + )); + + ret.arguments.emplace_back(parseExpression()); + if (i != args - 1) + { + if (currentToken() != Token::Comma) + fatalParserError(string( + "Expected ',' (instruction \"" + + instructionNames().at(instr) + + "\" expects " + + to_string(args) + + " arguments)" + )); + else + advance(); + } + } + ret.location.end = endPosition(); + if (currentToken() == Token::Comma) + fatalParserError(string( + "Expected ')' (instruction \"" + + instructionNames().at(instr) + + "\" expects " + + to_string(args) + + " arguments)" + )); + expectToken(Token::RParen); + return ret; + } + else if (_initialOp.type() == typeid(Identifier)) + { + FunctionCall ret; + ret.functionName = std::move(boost::get<Identifier>(_initialOp)); + ret.location = ret.functionName.location; + expectToken(Token::LParen); + while (currentToken() != Token::RParen) + { + ret.arguments.emplace_back(parseExpression()); + if (currentToken() == Token::RParen) + break; + expectToken(Token::Comma); + } + ret.location.end = endPosition(); + expectToken(Token::RParen); + return ret; + } + else + fatalParserError( + m_flavour == AsmFlavour::Yul ? + "Function name expected." : + "Assembly instruction or function name required in front of \"(\")" + ); + + return {}; +} + +TypedName Parser::parseTypedName() +{ + RecursionGuard recursionGuard(*this); + TypedName typedName = createWithLocation<TypedName>(); + typedName.name = YulString{expectAsmIdentifier()}; + if (m_flavour == AsmFlavour::Yul) + { + expectToken(Token::Colon); + typedName.location.end = endPosition(); + typedName.type = YulString{expectAsmIdentifier()}; + } + return typedName; +} + +string Parser::expectAsmIdentifier() +{ + string name = currentLiteral(); + if (m_flavour == AsmFlavour::Yul) + { + switch (currentToken()) + { + case Token::Return: + case Token::Byte: + case Token::Address: + case Token::Bool: + advance(); + return name; + default: + break; + } + } + else if (instructions().count(name)) + fatalParserError("Cannot use instruction names for identifier names."); + expectToken(Token::Identifier); + return name; +} + +bool Parser::isValidNumberLiteral(string const& _literal) +{ + try + { + // Try to convert _literal to u256. + auto tmp = u256(_literal); + (void) tmp; + } + catch (...) + { + return false; + } + if (boost::starts_with(_literal, "0x")) + return true; + else + return _literal.find_first_not_of("0123456789") == string::npos; +} diff --git a/libyul/AsmParser.h b/libyul/AsmParser.h new file mode 100644 index 00000000..9e13799a --- /dev/null +++ b/libyul/AsmParser.h @@ -0,0 +1,95 @@ +/* + 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/>. +*/ +/** + * @author Christian <c@ethdev.com> + * @date 2016 + * Solidity inline assembly parser. + */ + +#pragma once + +#include <memory> +#include <vector> +#include <libsolidity/inlineasm/AsmData.h> +#include <liblangutil/SourceLocation.h> +#include <liblangutil/Scanner.h> +#include <liblangutil/ParserBase.h> + +namespace dev +{ +namespace solidity +{ +namespace assembly +{ + +class Parser: public langutil::ParserBase +{ +public: + explicit Parser(langutil::ErrorReporter& _errorReporter, AsmFlavour _flavour = AsmFlavour::Loose): + ParserBase(_errorReporter), m_flavour(_flavour) {} + + /// Parses an inline assembly block starting with `{` and ending with `}`. + /// @param _reuseScanner if true, do check for end of input after the `}`. + /// @returns an empty shared pointer on error. + std::shared_ptr<Block> parse(std::shared_ptr<langutil::Scanner> const& _scanner, bool _reuseScanner); + +protected: + using ElementaryOperation = boost::variant<assembly::Instruction, assembly::Literal, assembly::Identifier>; + + /// Creates an inline assembly node with the given source location. + template <class T> T createWithLocation(langutil::SourceLocation const& _loc = {}) const + { + T r; + r.location = _loc; + if (r.location.isEmpty()) + { + r.location.start = position(); + r.location.end = endPosition(); + } + if (!r.location.sourceName) + r.location.sourceName = sourceName(); + return r; + } + langutil::SourceLocation location() const { return {position(), endPosition(), sourceName()}; } + + Block parseBlock(); + Statement parseStatement(); + Case parseCase(); + ForLoop parseForLoop(); + /// Parses a functional expression that has to push exactly one stack element + assembly::Expression parseExpression(); + static std::map<std::string, dev::solidity::Instruction> const& instructions(); + static std::map<dev::solidity::Instruction, std::string> const& instructionNames(); + /// Parses an elementary operation, i.e. a literal, identifier or instruction. + /// This will parse instructions even in strict mode as part of the full parser + /// for FunctionalInstruction. + ElementaryOperation parseElementaryOperation(); + VariableDeclaration parseVariableDeclaration(); + FunctionDefinition parseFunctionDefinition(); + assembly::Expression parseCall(ElementaryOperation&& _initialOp); + TypedName parseTypedName(); + std::string expectAsmIdentifier(); + + static bool isValidNumberLiteral(std::string const& _literal); + +private: + AsmFlavour m_flavour = AsmFlavour::Loose; +}; + +} +} +} diff --git a/libyul/AsmPrinter.cpp b/libyul/AsmPrinter.cpp new file mode 100644 index 00000000..7151fcfa --- /dev/null +++ b/libyul/AsmPrinter.cpp @@ -0,0 +1,250 @@ +/* + 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/>. +*/ +/** + * @author Christian <c@ethdev.com> + * @date 2017 + * Converts a parsed assembly into its textual form. + */ + +#include <libsolidity/inlineasm/AsmPrinter.h> +#include <libsolidity/inlineasm/AsmData.h> +#include <liblangutil/Exceptions.h> + +#include <libdevcore/CommonData.h> + +#include <boost/algorithm/string.hpp> +#include <boost/algorithm/string/replace.hpp> +#include <boost/range/adaptor/transformed.hpp> + +#include <memory> +#include <functional> + +using namespace std; +using namespace dev; +using namespace dev::solidity; +using namespace dev::solidity::assembly; + +//@TODO source locations + +string AsmPrinter::operator()(assembly::Instruction const& _instruction) +{ + solAssert(!m_yul, ""); + solAssert(isValidInstruction(_instruction.instruction), "Invalid instruction"); + return boost::to_lower_copy(instructionInfo(_instruction.instruction).name); +} + +string AsmPrinter::operator()(assembly::Literal const& _literal) +{ + switch (_literal.kind) + { + case LiteralKind::Number: + solAssert(isValidDecimal(_literal.value.str()) || isValidHex(_literal.value.str()), "Invalid number literal"); + return _literal.value.str() + appendTypeName(_literal.type); + case LiteralKind::Boolean: + solAssert(_literal.value.str() == "true" || _literal.value.str() == "false", "Invalid bool literal."); + return ((_literal.value.str() == "true") ? "true" : "false") + appendTypeName(_literal.type); + case LiteralKind::String: + break; + } + + string out; + for (char c: _literal.value.str()) + if (c == '\\') + out += "\\\\"; + else if (c == '"') + out += "\\\""; + else if (c == '\b') + out += "\\b"; + else if (c == '\f') + out += "\\f"; + else if (c == '\n') + out += "\\n"; + else if (c == '\r') + out += "\\r"; + else if (c == '\t') + out += "\\t"; + else if (c == '\v') + out += "\\v"; + else if (!isprint(c, locale::classic())) + { + ostringstream o; + o << std::hex << setfill('0') << setw(2) << (unsigned)(unsigned char)(c); + out += "\\x" + o.str(); + } + else + out += c; + return "\"" + out + "\"" + appendTypeName(_literal.type); +} + +string AsmPrinter::operator()(assembly::Identifier const& _identifier) +{ + solAssert(!_identifier.name.empty(), "Invalid identifier."); + return _identifier.name.str(); +} + +string AsmPrinter::operator()(assembly::FunctionalInstruction const& _functionalInstruction) +{ + solAssert(!m_yul, ""); + solAssert(isValidInstruction(_functionalInstruction.instruction), "Invalid instruction"); + return + boost::to_lower_copy(instructionInfo(_functionalInstruction.instruction).name) + + "(" + + boost::algorithm::join( + _functionalInstruction.arguments | boost::adaptors::transformed(boost::apply_visitor(*this)), + ", ") + + ")"; +} + +string AsmPrinter::operator()(ExpressionStatement const& _statement) +{ + return boost::apply_visitor(*this, _statement.expression); +} + +string AsmPrinter::operator()(assembly::Label const& _label) +{ + solAssert(!m_yul, ""); + solAssert(!_label.name.empty(), "Invalid label."); + return _label.name.str() + ":"; +} + +string AsmPrinter::operator()(assembly::StackAssignment const& _assignment) +{ + solAssert(!m_yul, ""); + solAssert(!_assignment.variableName.name.empty(), "Invalid variable name."); + return "=: " + (*this)(_assignment.variableName); +} + +string AsmPrinter::operator()(assembly::Assignment const& _assignment) +{ + solAssert(_assignment.variableNames.size() >= 1, ""); + string variables = (*this)(_assignment.variableNames.front()); + for (size_t i = 1; i < _assignment.variableNames.size(); ++i) + variables += ", " + (*this)(_assignment.variableNames[i]); + return variables + " := " + boost::apply_visitor(*this, *_assignment.value); +} + +string AsmPrinter::operator()(assembly::VariableDeclaration const& _variableDeclaration) +{ + string out = "let "; + out += boost::algorithm::join( + _variableDeclaration.variables | boost::adaptors::transformed( + [this](TypedName argument) { return formatTypedName(argument); } + ), + ", " + ); + if (_variableDeclaration.value) + { + out += " := "; + out += boost::apply_visitor(*this, *_variableDeclaration.value); + } + return out; +} + +string AsmPrinter::operator()(assembly::FunctionDefinition const& _functionDefinition) +{ + solAssert(!_functionDefinition.name.empty(), "Invalid function name."); + string out = "function " + _functionDefinition.name.str() + "("; + out += boost::algorithm::join( + _functionDefinition.parameters | boost::adaptors::transformed( + [this](TypedName argument) { return formatTypedName(argument); } + ), + ", " + ); + out += ")"; + if (!_functionDefinition.returnVariables.empty()) + { + out += " -> "; + out += boost::algorithm::join( + _functionDefinition.returnVariables | boost::adaptors::transformed( + [this](TypedName argument) { return formatTypedName(argument); } + ), + ", " + ); + } + + return out + "\n" + (*this)(_functionDefinition.body); +} + +string AsmPrinter::operator()(assembly::FunctionCall const& _functionCall) +{ + return + (*this)(_functionCall.functionName) + "(" + + boost::algorithm::join( + _functionCall.arguments | boost::adaptors::transformed(boost::apply_visitor(*this)), + ", " ) + + ")"; +} + +string AsmPrinter::operator()(If const& _if) +{ + solAssert(_if.condition, "Invalid if condition."); + return "if " + boost::apply_visitor(*this, *_if.condition) + "\n" + (*this)(_if.body); +} + +string AsmPrinter::operator()(Switch const& _switch) +{ + solAssert(_switch.expression, "Invalid expression pointer."); + string out = "switch " + boost::apply_visitor(*this, *_switch.expression); + for (auto const& _case: _switch.cases) + { + if (!_case.value) + out += "\ndefault "; + else + out += "\ncase " + (*this)(*_case.value) + " "; + out += (*this)(_case.body); + } + return out; +} + +string AsmPrinter::operator()(assembly::ForLoop const& _forLoop) +{ + solAssert(_forLoop.condition, "Invalid for loop condition."); + string out = "for "; + out += (*this)(_forLoop.pre); + out += "\n"; + out += boost::apply_visitor(*this, *_forLoop.condition); + out += "\n"; + out += (*this)(_forLoop.post); + out += "\n"; + out += (*this)(_forLoop.body); + return out; +} + +string AsmPrinter::operator()(Block const& _block) +{ + if (_block.statements.empty()) + return "{\n}"; + string body = boost::algorithm::join( + _block.statements | boost::adaptors::transformed(boost::apply_visitor(*this)), + "\n" + ); + boost::replace_all(body, "\n", "\n "); + return "{\n " + body + "\n}"; +} + +string AsmPrinter::formatTypedName(TypedName _variable) const +{ + solAssert(!_variable.name.empty(), "Invalid variable name."); + return _variable.name.str() + appendTypeName(_variable.type); +} + +string AsmPrinter::appendTypeName(YulString _type) const +{ + if (m_yul) + return ":" + _type.str(); + return ""; +} diff --git a/libyul/AsmPrinter.h b/libyul/AsmPrinter.h new file mode 100644 index 00000000..72048975 --- /dev/null +++ b/libyul/AsmPrinter.h @@ -0,0 +1,68 @@ +/* + 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/>. +*/ +/** + * @author Christian <c@ethdev.com> + * @date 2017 + * Converts a parsed assembly into its textual form. + */ + +#pragma once + +#include <libsolidity/inlineasm/AsmDataForward.h> + +#include <libyul/YulString.h> + +#include <boost/variant.hpp> + +namespace dev +{ +namespace solidity +{ +namespace assembly +{ + +class AsmPrinter: public boost::static_visitor<std::string> +{ +public: + explicit AsmPrinter(bool _yul = false): m_yul(_yul) {} + + std::string operator()(assembly::Instruction const& _instruction); + std::string operator()(assembly::Literal const& _literal); + std::string operator()(assembly::Identifier const& _identifier); + std::string operator()(assembly::FunctionalInstruction const& _functionalInstruction); + std::string operator()(assembly::ExpressionStatement const& _expr); + std::string operator()(assembly::Label const& _label); + std::string operator()(assembly::StackAssignment const& _assignment); + std::string operator()(assembly::Assignment const& _assignment); + std::string operator()(assembly::VariableDeclaration const& _variableDeclaration); + std::string operator()(assembly::FunctionDefinition const& _functionDefinition); + std::string operator()(assembly::FunctionCall const& _functionCall); + std::string operator()(assembly::If const& _if); + std::string operator()(assembly::Switch const& _switch); + std::string operator()(assembly::ForLoop const& _forLoop); + std::string operator()(assembly::Block const& _block); + +private: + std::string formatTypedName(TypedName _variable) const; + std::string appendTypeName(yul::YulString _type) const; + + bool m_yul = false; +}; + +} +} +} diff --git a/libyul/AsmScope.cpp b/libyul/AsmScope.cpp new file mode 100644 index 00000000..10893b96 --- /dev/null +++ b/libyul/AsmScope.cpp @@ -0,0 +1,98 @@ +/* + 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/>. +*/ +/** + * Scopes for identifiers. + */ + +#include <libsolidity/inlineasm/AsmScope.h> + +using namespace std; +using namespace dev; +using namespace dev::solidity::assembly; + +bool Scope::registerLabel(yul::YulString _name) +{ + if (exists(_name)) + return false; + identifiers[_name] = Label(); + return true; +} + +bool Scope::registerVariable(yul::YulString _name, YulType const& _type) +{ + if (exists(_name)) + return false; + Variable variable; + variable.type = _type; + identifiers[_name] = variable; + return true; +} + +bool Scope::registerFunction(yul::YulString _name, std::vector<YulType> const& _arguments, std::vector<YulType> const& _returns) +{ + if (exists(_name)) + return false; + identifiers[_name] = Function{_arguments, _returns}; + return true; +} + +Scope::Identifier* Scope::lookup(yul::YulString _name) +{ + bool crossedFunctionBoundary = false; + for (Scope* s = this; s; s = s->superScope) + { + auto id = s->identifiers.find(_name); + if (id != s->identifiers.end()) + { + if (crossedFunctionBoundary && id->second.type() == typeid(Scope::Variable)) + return nullptr; + else + return &id->second; + } + + if (s->functionScope) + crossedFunctionBoundary = true; + } + return nullptr; +} + +bool Scope::exists(yul::YulString _name) const +{ + if (identifiers.count(_name)) + return true; + else if (superScope) + return superScope->exists(_name); + else + return false; +} + +size_t Scope::numberOfVariables() const +{ + size_t count = 0; + for (auto const& identifier: identifiers) + if (identifier.second.type() == typeid(Scope::Variable)) + count++; + return count; +} + +bool Scope::insideFunction() const +{ + for (Scope const* s = this; s; s = s->superScope) + if (s->functionScope) + return true; + return false; +} diff --git a/libyul/AsmScope.h b/libyul/AsmScope.h new file mode 100644 index 00000000..12c05716 --- /dev/null +++ b/libyul/AsmScope.h @@ -0,0 +1,105 @@ +/* + 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/>. +*/ +/** + * Scopes for identifiers. + */ + +#pragma once + +#include <liblangutil/Exceptions.h> + +#include <libyul/YulString.h> + +#include <libdevcore/Visitor.h> + +#include <boost/variant.hpp> +#include <boost/optional.hpp> + +#include <functional> +#include <memory> + +namespace dev +{ +namespace solidity +{ +namespace assembly +{ + +struct Scope +{ + using YulType = yul::YulString; + using LabelID = size_t; + + struct Variable { YulType type; }; + struct Label { }; + struct Function + { + std::vector<YulType> arguments; + std::vector<YulType> returns; + }; + + using Identifier = boost::variant<Variable, Label, Function>; + using Visitor = GenericVisitor<Variable const, Label const, Function const>; + using NonconstVisitor = GenericVisitor<Variable, Label, Function>; + + bool registerVariable(yul::YulString _name, YulType const& _type); + bool registerLabel(yul::YulString _name); + bool registerFunction( + yul::YulString _name, + std::vector<YulType> const& _arguments, + std::vector<YulType> const& _returns + ); + + /// Looks up the identifier in this or super scopes and returns a valid pointer if found + /// or a nullptr if not found. Variable lookups up across function boundaries will fail, as + /// will any lookups across assembly boundaries. + /// The pointer will be invalidated if the scope is modified. + /// @param _crossedFunction if true, we already crossed a function boundary during recursive lookup + Identifier* lookup(yul::YulString _name); + /// Looks up the identifier in this and super scopes (will not find variables across function + /// boundaries and generally stops at assembly boundaries) and calls the visitor, returns + /// false if not found. + template <class V> + bool lookup(yul::YulString _name, V const& _visitor) + { + if (Identifier* id = lookup(_name)) + { + boost::apply_visitor(_visitor, *id); + return true; + } + else + return false; + } + /// @returns true if the name exists in this scope or in super scopes (also searches + /// across function and assembly boundaries). + bool exists(yul::YulString _name) const; + + /// @returns the number of variables directly registered inside the scope. + size_t numberOfVariables() const; + /// @returns true if this scope is inside a function. + bool insideFunction() const; + + Scope* superScope = nullptr; + /// If true, variables from the super scope are not visible here (other identifiers are), + /// but they are still taken into account to prevent shadowing. + bool functionScope = false; + std::map<yul::YulString, Identifier> identifiers; +}; + +} +} +} diff --git a/libyul/AsmScopeFiller.cpp b/libyul/AsmScopeFiller.cpp new file mode 100644 index 00000000..09934bd8 --- /dev/null +++ b/libyul/AsmScopeFiller.cpp @@ -0,0 +1,181 @@ +/* + 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/>. +*/ +/** + * Module responsible for registering identifiers inside their scopes. + */ + +#include <libsolidity/inlineasm/AsmScopeFiller.h> + +#include <libsolidity/inlineasm/AsmData.h> +#include <libsolidity/inlineasm/AsmScope.h> +#include <libsolidity/inlineasm/AsmAnalysisInfo.h> + +#include <liblangutil/ErrorReporter.h> +#include <liblangutil/Exceptions.h> + +#include <libdevcore/CommonData.h> + +#include <boost/range/adaptor/reversed.hpp> + +#include <memory> +#include <functional> + +using namespace std; +using namespace dev; +using namespace langutil; +using namespace dev::solidity; +using namespace dev::solidity::assembly; + +ScopeFiller::ScopeFiller(AsmAnalysisInfo& _info, ErrorReporter& _errorReporter): + m_info(_info), m_errorReporter(_errorReporter) +{ + m_currentScope = &scope(nullptr); +} + +bool ScopeFiller::operator()(ExpressionStatement const& _expr) +{ + return boost::apply_visitor(*this, _expr.expression); +} + +bool ScopeFiller::operator()(Label const& _item) +{ + if (!m_currentScope->registerLabel(_item.name)) + { + //@TODO secondary location + m_errorReporter.declarationError( + _item.location, + "Label name " + _item.name.str() + " already taken in this scope." + ); + return false; + } + return true; +} + +bool ScopeFiller::operator()(assembly::VariableDeclaration const& _varDecl) +{ + for (auto const& variable: _varDecl.variables) + if (!registerVariable(variable, _varDecl.location, *m_currentScope)) + return false; + return true; +} + +bool ScopeFiller::operator()(assembly::FunctionDefinition const& _funDef) +{ + bool success = true; + vector<Scope::YulType> arguments; + for (auto const& _argument: _funDef.parameters) + arguments.emplace_back(_argument.type.str()); + vector<Scope::YulType> returns; + for (auto const& _return: _funDef.returnVariables) + returns.emplace_back(_return.type.str()); + if (!m_currentScope->registerFunction(_funDef.name, arguments, returns)) + { + //@TODO secondary location + m_errorReporter.declarationError( + _funDef.location, + "Function name " + _funDef.name.str() + " already taken in this scope." + ); + success = false; + } + + auto virtualBlock = m_info.virtualBlocks[&_funDef] = make_shared<Block>(); + Scope& varScope = scope(virtualBlock.get()); + varScope.superScope = m_currentScope; + m_currentScope = &varScope; + varScope.functionScope = true; + for (auto const& var: _funDef.parameters + _funDef.returnVariables) + if (!registerVariable(var, _funDef.location, varScope)) + success = false; + + if (!(*this)(_funDef.body)) + success = false; + + solAssert(m_currentScope == &varScope, ""); + m_currentScope = m_currentScope->superScope; + + return success; +} + +bool ScopeFiller::operator()(If const& _if) +{ + return (*this)(_if.body); +} + +bool ScopeFiller::operator()(Switch const& _switch) +{ + bool success = true; + for (auto const& _case: _switch.cases) + if (!(*this)(_case.body)) + success = false; + return success; +} + +bool ScopeFiller::operator()(ForLoop const& _forLoop) +{ + Scope* originalScope = m_currentScope; + + bool success = true; + if (!(*this)(_forLoop.pre)) + success = false; + m_currentScope = &scope(&_forLoop.pre); + if (!boost::apply_visitor(*this, *_forLoop.condition)) + success = false; + if (!(*this)(_forLoop.body)) + success = false; + if (!(*this)(_forLoop.post)) + success = false; + + m_currentScope = originalScope; + + return success; +} + +bool ScopeFiller::operator()(Block const& _block) +{ + bool success = true; + scope(&_block).superScope = m_currentScope; + m_currentScope = &scope(&_block); + + for (auto const& s: _block.statements) + if (!boost::apply_visitor(*this, s)) + success = false; + + m_currentScope = m_currentScope->superScope; + return success; +} + +bool ScopeFiller::registerVariable(TypedName const& _name, SourceLocation const& _location, Scope& _scope) +{ + if (!_scope.registerVariable(_name.name, _name.type)) + { + //@TODO secondary location + m_errorReporter.declarationError( + _location, + "Variable name " + _name.name.str() + " already taken in this scope." + ); + return false; + } + return true; +} + +Scope& ScopeFiller::scope(Block const* _block) +{ + auto& scope = m_info.scopes[_block]; + if (!scope) + scope = make_shared<Scope>(); + return *scope; +} diff --git a/libyul/AsmScopeFiller.h b/libyul/AsmScopeFiller.h new file mode 100644 index 00000000..7454fd6c --- /dev/null +++ b/libyul/AsmScopeFiller.h @@ -0,0 +1,88 @@ +/* + 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/>. +*/ +/** + * Module responsible for registering identifiers inside their scopes. + */ + +#pragma once + +#include <libsolidity/inlineasm/AsmDataForward.h> + +#include <boost/variant.hpp> + +#include <functional> +#include <memory> + +namespace langutil +{ +class ErrorReporter; +struct SourceLocation; +} + +namespace dev +{ +namespace solidity +{ +namespace assembly +{ + +struct TypedName; +struct Scope; +struct AsmAnalysisInfo; + +/** + * Fills scopes with identifiers and checks for name clashes. + * Does not resolve references. + */ +class ScopeFiller: public boost::static_visitor<bool> +{ +public: + ScopeFiller(AsmAnalysisInfo& _info, langutil::ErrorReporter& _errorReporter); + + bool operator()(assembly::Instruction const&) { return true; } + bool operator()(assembly::Literal const&) { return true; } + bool operator()(assembly::Identifier const&) { return true; } + bool operator()(assembly::FunctionalInstruction const&) { return true; } + bool operator()(assembly::ExpressionStatement const& _expr); + bool operator()(assembly::Label const& _label); + bool operator()(assembly::StackAssignment const&) { return true; } + bool operator()(assembly::Assignment const&) { return true; } + bool operator()(assembly::VariableDeclaration const& _variableDeclaration); + bool operator()(assembly::FunctionDefinition const& _functionDefinition); + bool operator()(assembly::FunctionCall const&) { return true; } + bool operator()(assembly::If const& _if); + bool operator()(assembly::Switch const& _switch); + bool operator()(assembly::ForLoop const& _forLoop); + bool operator()(assembly::Block const& _block); + +private: + bool registerVariable( + TypedName const& _name, + langutil::SourceLocation const& _location, + Scope& _scope + ); + + Scope& scope(assembly::Block const* _block); + + Scope* m_currentScope = nullptr; + AsmAnalysisInfo& m_info; + langutil::ErrorReporter& m_errorReporter; +}; + +} +} +} |