diff options
author | Daniel Kirchner <daniel@ekpyron.org> | 2018-05-04 21:58:10 +0800 |
---|---|---|
committer | Daniel Kirchner <daniel@ekpyron.org> | 2018-05-15 02:23:40 +0800 |
commit | 995623f0fa37fdaa6be3dd2d95540fc123ce4248 (patch) | |
tree | 100a146f59c86364e1080abff42c794d499e4767 | |
parent | ab63ab1cbb2f3fe68d2db991710b53e2c8c25f2d (diff) | |
download | dexon-solidity-995623f0fa37fdaa6be3dd2d95540fc123ce4248.tar.gz dexon-solidity-995623f0fa37fdaa6be3dd2d95540fc123ce4248.tar.zst dexon-solidity-995623f0fa37fdaa6be3dd2d95540fc123ce4248.zip |
Add control flow graph.
-rw-r--r-- | libsolidity/analysis/ControlFlowBuilder.cpp | 370 | ||||
-rw-r--r-- | libsolidity/analysis/ControlFlowBuilder.h | 143 | ||||
-rw-r--r-- | libsolidity/analysis/ControlFlowGraph.cpp | 136 | ||||
-rw-r--r-- | libsolidity/analysis/ControlFlowGraph.h | 148 | ||||
-rw-r--r-- | libsolidity/interface/CompilerStack.cpp | 9 |
5 files changed, 806 insertions, 0 deletions
diff --git a/libsolidity/analysis/ControlFlowBuilder.cpp b/libsolidity/analysis/ControlFlowBuilder.cpp new file mode 100644 index 00000000..35d7687c --- /dev/null +++ b/libsolidity/analysis/ControlFlowBuilder.cpp @@ -0,0 +1,370 @@ +/* + 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/>. +*/ + +#include <libsolidity/analysis/ControlFlowBuilder.h> + +using namespace dev; +using namespace solidity; +using namespace std; + +ControlFlowBuilder::ControlFlowBuilder(CFG::NodeContainer& _nodeContainer, FunctionFlow const& _functionFlow): + m_nodeContainer(_nodeContainer), m_currentFunctionFlow(_functionFlow), m_currentNode(_functionFlow.entry) +{ +} + +unique_ptr<FunctionFlow> ControlFlowBuilder::createFunctionFlow( + CFG::NodeContainer& _nodeContainer, + FunctionDefinition const& _function +) +{ + auto functionFlow = unique_ptr<FunctionFlow>(new FunctionFlow()); + functionFlow->entry = _nodeContainer.newNode(); + functionFlow->exit = _nodeContainer.newNode(); + functionFlow->revert = _nodeContainer.newNode(); + ControlFlowBuilder builder(_nodeContainer, *functionFlow); + builder.appendControlFlow(_function); + connect(builder.m_currentNode, functionFlow->exit); + return functionFlow; +} + + +unique_ptr<ModifierFlow> ControlFlowBuilder::createModifierFlow( + CFG::NodeContainer& _nodeContainer, + ModifierDefinition const& _modifier +) +{ + auto modifierFlow = unique_ptr<ModifierFlow>(new ModifierFlow()); + modifierFlow->entry = _nodeContainer.newNode(); + modifierFlow->exit = _nodeContainer.newNode(); + modifierFlow->revert = _nodeContainer.newNode(); + modifierFlow->placeholderEntry = _nodeContainer.newNode(); + modifierFlow->placeholderExit = _nodeContainer.newNode(); + ControlFlowBuilder builder(_nodeContainer, *modifierFlow); + builder.appendControlFlow(_modifier); + connect(builder.m_currentNode, modifierFlow->exit); + return modifierFlow; +} + +bool ControlFlowBuilder::visit(BinaryOperation const& _operation) +{ + solAssert(!!m_currentNode, ""); + + switch(_operation.getOperator()) + { + case Token::Or: + case Token::And: + { + appendControlFlow(_operation.leftExpression()); + + auto nodes = splitFlow<2>(); + nodes[0] = createFlow(nodes[0], _operation.rightExpression()); + mergeFlow(nodes, nodes[1]); + + return false; + } + default: + break; + } + return ASTConstVisitor::visit(_operation); +} + +bool ControlFlowBuilder::visit(Conditional const& _conditional) +{ + solAssert(!!m_currentNode, ""); + + _conditional.condition().accept(*this); + + auto nodes = splitFlow<2>(); + + nodes[0] = createFlow(nodes[0], _conditional.trueExpression()); + nodes[1] = createFlow(nodes[1], _conditional.falseExpression()); + + mergeFlow(nodes); + + return false; +} + +bool ControlFlowBuilder::visit(IfStatement const& _ifStatement) +{ + solAssert(!!m_currentNode, ""); + + _ifStatement.condition().accept(*this); + + auto nodes = splitFlow<2>(); + nodes[0] = createFlow(nodes[0], _ifStatement.trueStatement()); + + if (_ifStatement.falseStatement()) + { + nodes[1] = createFlow(nodes[1], *_ifStatement.falseStatement()); + mergeFlow(nodes); + } + else + mergeFlow(nodes, nodes[1]); + + return false; +} + +bool ControlFlowBuilder::visit(ForStatement const& _forStatement) +{ + solAssert(!!m_currentNode, ""); + + if (_forStatement.initializationExpression()) + _forStatement.initializationExpression()->accept(*this); + + auto condition = createLabelHere(); + + if (_forStatement.condition()) + appendControlFlow(*_forStatement.condition()); + + auto loopExpression = newLabel(); + auto nodes = splitFlow<2>(); + auto afterFor = nodes[1]; + m_currentNode = nodes[0]; + + { + BreakContinueScope scope(*this, afterFor, loopExpression); + appendControlFlow(_forStatement.body()); + } + + placeAndConnectLabel(loopExpression); + + if (auto expression = _forStatement.loopExpression()) + appendControlFlow(*expression); + + connect(m_currentNode, condition); + m_currentNode = afterFor; + + return false; +} + +bool ControlFlowBuilder::visit(WhileStatement const& _whileStatement) +{ + solAssert(!!m_currentNode, ""); + + if (_whileStatement.isDoWhile()) + { + auto afterWhile = newLabel(); + auto whileBody = createLabelHere(); + + { + // Note that "continue" in this case currently indeed jumps to whileBody + // and not to the condition. This is inconsistent with JavaScript and C and + // therefore a bug. This will be fixed in the future (planned for 0.5.0) + // and the Control Flow Graph will have to be adjusted accordingly. + BreakContinueScope scope(*this, afterWhile, whileBody); + appendControlFlow(_whileStatement.body()); + } + appendControlFlow(_whileStatement.condition()); + + connect(m_currentNode, whileBody); + placeAndConnectLabel(afterWhile); + } + else + { + auto whileCondition = createLabelHere(); + + appendControlFlow(_whileStatement.condition()); + + auto nodes = splitFlow<2>(); + + auto whileBody = nodes[0]; + auto afterWhile = nodes[1]; + + m_currentNode = whileBody; + { + BreakContinueScope scope(*this, afterWhile, whileCondition); + appendControlFlow(_whileStatement.body()); + } + + connect(m_currentNode, whileCondition); + + m_currentNode = afterWhile; + } + + + return false; +} + +bool ControlFlowBuilder::visit(Break const&) +{ + solAssert(!!m_currentNode, ""); + solAssert(!!m_breakJump, ""); + connect(m_currentNode, m_breakJump); + m_currentNode = newLabel(); + return false; +} + +bool ControlFlowBuilder::visit(Continue const&) +{ + solAssert(!!m_currentNode, ""); + solAssert(!!m_continueJump, ""); + connect(m_currentNode, m_continueJump); + m_currentNode = newLabel(); + return false; +} + +bool ControlFlowBuilder::visit(Throw const&) +{ + solAssert(!!m_currentNode, ""); + solAssert(!!m_currentFunctionFlow.revert, ""); + connect(m_currentNode, m_currentFunctionFlow.revert); + m_currentNode = newLabel(); + return false; +} + +bool ControlFlowBuilder::visit(Block const&) +{ + solAssert(!!m_currentNode, ""); + createLabelHere(); + return true; +} + +void ControlFlowBuilder::endVisit(Block const&) +{ + solAssert(!!m_currentNode, ""); + createLabelHere(); +} + +bool ControlFlowBuilder::visit(Return const& _return) +{ + solAssert(!!m_currentNode, ""); + solAssert(!!m_currentFunctionFlow.exit, ""); + solAssert(!m_currentNode->block.returnStatement, ""); + m_currentNode->block.returnStatement = &_return; + connect(m_currentNode, m_currentFunctionFlow.exit); + m_currentNode = newLabel(); + return true; +} + + +bool ControlFlowBuilder::visit(PlaceholderStatement const&) +{ + solAssert(!!m_currentNode, ""); + auto modifierFlow = dynamic_cast<ModifierFlow const*>(&m_currentFunctionFlow); + solAssert(!!modifierFlow, ""); + + connect(m_currentNode, modifierFlow->placeholderEntry); + + m_currentNode = newLabel(); + + connect(modifierFlow->placeholderExit, m_currentNode); + return false; +} + +bool ControlFlowBuilder::visitNode(ASTNode const& node) +{ + solAssert(!!m_currentNode, ""); + if (auto const* expression = dynamic_cast<Expression const*>(&node)) + m_currentNode->block.expressions.emplace_back(expression); + else if (auto const* variableDeclaration = dynamic_cast<VariableDeclaration const*>(&node)) + m_currentNode->block.variableDeclarations.emplace_back(variableDeclaration); + else if (auto const* assembly = dynamic_cast<InlineAssembly const*>(&node)) + m_currentNode->block.inlineAssemblyStatements.emplace_back(assembly); + + return true; +} + +bool ControlFlowBuilder::visit(FunctionCall const& _functionCall) +{ + solAssert(!!m_currentNode, ""); + solAssert(!!_functionCall.expression().annotation().type, ""); + + if (auto functionType = dynamic_pointer_cast<FunctionType const>(_functionCall.expression().annotation().type)) + switch (functionType->kind()) + { + case FunctionType::Kind::Revert: + solAssert(!!m_currentFunctionFlow.revert, ""); + _functionCall.expression().accept(*this); + ASTNode::listAccept(_functionCall.arguments(), *this); + connect(m_currentNode, m_currentFunctionFlow.revert); + m_currentNode = newLabel(); + return false; + case FunctionType::Kind::Require: + case FunctionType::Kind::Assert: + { + solAssert(!!m_currentFunctionFlow.revert, ""); + _functionCall.expression().accept(*this); + ASTNode::listAccept(_functionCall.arguments(), *this); + connect(m_currentNode, m_currentFunctionFlow.revert); + auto nextNode = newLabel(); + connect(m_currentNode, nextNode); + m_currentNode = nextNode; + return false; + } + default: + break; + } + return ASTConstVisitor::visit(_functionCall); +} + +void ControlFlowBuilder::appendControlFlow(ASTNode const& _node) +{ + _node.accept(*this); +} + +CFGNode* ControlFlowBuilder::createFlow(CFGNode* _entry, ASTNode const& _node) +{ + auto oldCurrentNode = m_currentNode; + m_currentNode = _entry; + appendControlFlow(_node); + auto endNode = m_currentNode; + m_currentNode = oldCurrentNode; + return endNode; +} + +void ControlFlowBuilder::connect(CFGNode* _from, CFGNode* _to) +{ + solAssert(_from, ""); + solAssert(_to, ""); + _from->exits.push_back(_to); + _to->entries.push_back(_from); +} + +CFGNode* ControlFlowBuilder::newLabel() +{ + return m_nodeContainer.newNode(); +} + +CFGNode* ControlFlowBuilder::createLabelHere() +{ + auto label = m_nodeContainer.newNode(); + connect(m_currentNode, label); + m_currentNode = label; + return label; +} + +void ControlFlowBuilder::placeAndConnectLabel(CFGNode* _node) +{ + connect(m_currentNode, _node); + m_currentNode = _node; +} + +ControlFlowBuilder::BreakContinueScope::BreakContinueScope( + ControlFlowBuilder& _parser, + CFGNode* _breakJump, + CFGNode* _continueJump +): m_parser(_parser), m_origBreakJump(_parser.m_breakJump), m_origContinueJump(_parser.m_continueJump) +{ + m_parser.m_breakJump = _breakJump; + m_parser.m_continueJump = _continueJump; +} + +ControlFlowBuilder::BreakContinueScope::~BreakContinueScope() +{ + m_parser.m_breakJump = m_origBreakJump; + m_parser.m_continueJump = m_origContinueJump; +} diff --git a/libsolidity/analysis/ControlFlowBuilder.h b/libsolidity/analysis/ControlFlowBuilder.h new file mode 100644 index 00000000..e9d96e5f --- /dev/null +++ b/libsolidity/analysis/ControlFlowBuilder.h @@ -0,0 +1,143 @@ +/* + 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/>. +*/ + +#pragma once + +#include <libsolidity/analysis/ControlFlowGraph.h> +#include <libsolidity/ast/AST.h> +#include <libsolidity/ast/ASTVisitor.h> + +#include <array> +#include <memory> + +namespace dev { +namespace solidity { + +/** Helper class that builds the control flow of a function or modifier. + * Modifiers are not yet applied to the functions. This is done in a second + * step in the CFG class. + */ +class ControlFlowBuilder: private ASTConstVisitor +{ +public: + static std::unique_ptr<FunctionFlow> createFunctionFlow( + CFG::NodeContainer& _nodeContainer, + FunctionDefinition const& _function + ); + static std::unique_ptr<ModifierFlow> createModifierFlow( + CFG::NodeContainer& _nodeContainer, + ModifierDefinition const& _modifier + ); + +private: + explicit ControlFlowBuilder(CFG::NodeContainer& _nodeContainer, FunctionFlow const& _functionFlow); + + virtual bool visit(BinaryOperation const& _operation) override; + virtual bool visit(Conditional const& _conditional) override; + virtual bool visit(IfStatement const& _ifStatement) override; + virtual bool visit(ForStatement const& _forStatement) override; + virtual bool visit(WhileStatement const& _whileStatement) override; + virtual bool visit(Break const&) override; + virtual bool visit(Continue const&) override; + virtual bool visit(Throw const&) override; + virtual bool visit(Block const&) override; + virtual void endVisit(Block const&) override; + virtual bool visit(Return const& _return) override; + virtual bool visit(PlaceholderStatement const&) override; + virtual bool visit(FunctionCall const& _functionCall) override; + + + /// Appends the control flow of @a _node to the current control flow. + void appendControlFlow(ASTNode const& _node); + + /// Starts at @a _entry and parses the control flow of @a _node. + /// @returns The node at which the parsed control flow ends. + /// m_currentNode is not affected (it is saved and restored). + CFGNode* createFlow(CFGNode* _entry, ASTNode const& _node); + + /// Creates an arc from @a _from to @a _to. + static void connect(CFGNode* _from, CFGNode* _to); + + +protected: + virtual bool visitNode(ASTNode const& node) override; + +private: + + /// Splits the control flow starting at the current node into n paths. + /// m_currentNode is set to nullptr and has to be set manually or + /// using mergeFlow later. + template<size_t n> + std::array<CFGNode*, n> splitFlow() + { + std::array<CFGNode*, n> result; + for (auto& node: result) + { + node = m_nodeContainer.newNode(); + connect(m_currentNode, node); + } + m_currentNode = nullptr; + return result; + } + + /// Merges the control flow of @a _nodes to @a _endNode. + /// If @a _endNode is nullptr, a new node is creates and used as end node. + /// Sets the merge destination as current node. + /// Note: @a _endNode may be one of the nodes in @a _nodes. + template<size_t n> + void mergeFlow(std::array<CFGNode*, n> const& _nodes, CFGNode* _endNode = nullptr) + { + CFGNode* mergeDestination = (_endNode == nullptr) ? m_nodeContainer.newNode() : _endNode; + for (auto& node: _nodes) + if (node != mergeDestination) + connect(node, mergeDestination); + m_currentNode = mergeDestination; + } + + CFGNode* newLabel(); + CFGNode* createLabelHere(); + void placeAndConnectLabel(CFGNode *_node); + + CFG::NodeContainer& m_nodeContainer; + + /// The control flow of the function that is currently parsed. + /// Note: this can also be a ModifierFlow + FunctionFlow const& m_currentFunctionFlow; + + CFGNode* m_currentNode = nullptr; + + /// The current jump destination of break Statements. + CFGNode* m_breakJump = nullptr; + /// The current jump destination of continue Statements. + CFGNode* m_continueJump = nullptr; + + /// Helper class that replaces the break and continue jump destinations for the + /// current scope and restores the originals at the end of the scope. + class BreakContinueScope + { + public: + BreakContinueScope(ControlFlowBuilder& _parser, CFGNode* _breakJump, CFGNode* _continueJump); + ~BreakContinueScope(); + private: + ControlFlowBuilder& m_parser; + CFGNode* m_origBreakJump; + CFGNode* m_origContinueJump; + }; +}; + +} +} diff --git a/libsolidity/analysis/ControlFlowGraph.cpp b/libsolidity/analysis/ControlFlowGraph.cpp new file mode 100644 index 00000000..9b3da0eb --- /dev/null +++ b/libsolidity/analysis/ControlFlowGraph.cpp @@ -0,0 +1,136 @@ +/* + 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/>. +*/ + +#include <libsolidity/analysis/ControlFlowGraph.h> +#include <libsolidity/analysis/ControlFlowBuilder.h> + +#include <boost/range/adaptor/reversed.hpp> + +#include <algorithm> + +using namespace std; +using namespace dev::solidity; + +bool CFG::constructFlow(ASTNode const& _astRoot) +{ + _astRoot.accept(*this); + applyModifiers(); + return Error::containsOnlyWarnings(m_errorReporter.errors()); +} + + +bool CFG::visit(ModifierDefinition const& _modifier) +{ + m_modifierControlFlow[&_modifier] = ControlFlowBuilder::createModifierFlow(m_nodeContainer, _modifier); + return false; +} + +bool CFG::visit(FunctionDefinition const& _function) +{ + m_functionControlFlow[&_function] = ControlFlowBuilder::createFunctionFlow(m_nodeContainer, _function); + return false; +} + +FunctionFlow const& CFG::functionFlow(FunctionDefinition const& _function) const +{ + solAssert(m_functionControlFlow.count(&_function), ""); + return *m_functionControlFlow.find(&_function)->second; +} + +CFGNode* CFG::NodeContainer::newNode() +{ + m_nodes.emplace_back(new CFGNode()); + return m_nodes.back().get(); +} + +void CFG::applyModifiers() +{ + for (auto const& function: m_functionControlFlow) + { + for (auto const& modifierInvocation: boost::adaptors::reverse(function.first->modifiers())) + { + if (auto modifierDefinition = dynamic_cast<ModifierDefinition const*>( + modifierInvocation->name()->annotation().referencedDeclaration + )) + { + solAssert(m_modifierControlFlow.count(modifierDefinition), ""); + applyModifierFlowToFunctionFlow(*m_modifierControlFlow[modifierDefinition], function.second.get()); + } + } + } +} + +void CFG::applyModifierFlowToFunctionFlow( + ModifierFlow const& _modifierFlow, + FunctionFlow* _functionFlow +) +{ + solAssert(!!_functionFlow, ""); + + map<CFGNode*, CFGNode*> copySrcToCopyDst; + + // inherit the revert node of the function + copySrcToCopyDst[_modifierFlow.revert] = _functionFlow->revert; + + // replace the placeholder nodes by the function entry and exit + copySrcToCopyDst[_modifierFlow.placeholderEntry] = _functionFlow->entry; + copySrcToCopyDst[_modifierFlow.placeholderExit] = _functionFlow->exit; + + stack<CFGNode*> nodesToCopy; + nodesToCopy.push(_modifierFlow.entry); + + // map the modifier entry to a new node that will become the new function entry + copySrcToCopyDst[_modifierFlow.entry] = m_nodeContainer.newNode(); + + while (!nodesToCopy.empty()) + { + CFGNode* copySrcNode = nodesToCopy.top(); + nodesToCopy.pop(); + + solAssert(copySrcToCopyDst.count(copySrcNode), ""); + + CFGNode* copyDstNode = copySrcToCopyDst[copySrcNode]; + + copyDstNode->block = copySrcNode->block; + for (auto const& entry: copySrcNode->entries) + { + if (!copySrcToCopyDst.count(entry)) + { + copySrcToCopyDst[entry] = m_nodeContainer.newNode(); + nodesToCopy.push(entry); + } + copyDstNode->entries.emplace_back(copySrcToCopyDst[entry]); + } + for (auto const& exit: copySrcNode->exits) + { + if (!copySrcToCopyDst.count(exit)) + { + copySrcToCopyDst[exit] = m_nodeContainer.newNode(); + nodesToCopy.push(exit); + } + copyDstNode->exits.emplace_back(copySrcToCopyDst[exit]); + } + } + + // if the modifier control flow never reached its exit node, + // we need to create a new (disconnected) exit node now + if (!copySrcToCopyDst.count(_modifierFlow.exit)) + copySrcToCopyDst[_modifierFlow.exit] = m_nodeContainer.newNode(); + + _functionFlow->entry = copySrcToCopyDst[_modifierFlow.entry]; + _functionFlow->exit = copySrcToCopyDst[_modifierFlow.exit]; +}
\ No newline at end of file diff --git a/libsolidity/analysis/ControlFlowGraph.h b/libsolidity/analysis/ControlFlowGraph.h new file mode 100644 index 00000000..c646e4f1 --- /dev/null +++ b/libsolidity/analysis/ControlFlowGraph.h @@ -0,0 +1,148 @@ +/* + 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/>. +*/ + +#pragma once + +#include <libsolidity/ast/AST.h> +#include <libsolidity/ast/ASTVisitor.h> +#include <libsolidity/interface/ErrorReporter.h> + +#include <map> +#include <memory> +#include <stack> +#include <vector> + +namespace dev +{ +namespace solidity +{ + +/** Basic Control Flow Block. + * Basic block of control flow. Consists of a set of (unordered) AST nodes + * for which control flow is always linear. A basic control flow block + * encompasses at most one scope. Reverts are considered to break the control + * flow. + * @todo Handle function calls correctly. So far function calls are not considered + * to change the control flow. + */ +struct ControlFlowBlock +{ + /// All variable declarations inside this control flow block. + std::vector<VariableDeclaration const*> variableDeclarations; + /// All expressions inside this control flow block (this includes all subexpressions!). + std::vector<Expression const*> expressions; + /// All inline assembly statements inside in this control flow block. + std::vector<InlineAssembly const*> inlineAssemblyStatements; + /// If control flow returns in this node, the return statement is stored in returnStatement, + /// otherwise returnStatement is nullptr. + Return const* returnStatement = nullptr; +}; + +/** Node of the Control Flow Graph. + * The control flow is a directed graph connecting control flow blocks. + * An arc between two nodes indicates that the control flow can possibly + * move from its start node to its end node during execution. + */ +struct CFGNode +{ + /// Entry nodes. All CFG nodes from which control flow may move into this node. + std::vector<CFGNode*> entries; + /// Exit nodes. All CFG nodes to which control flow may continue after this node. + std::vector<CFGNode*> exits; + + /// Control flow in the node. + ControlFlowBlock block; +}; + +/** Describes the control flow of a function. */ +struct FunctionFlow +{ + virtual ~FunctionFlow() {} + /// Entry node. Control flow of the function starts here. + /// This node is empty and does not have any entries. + CFGNode* entry = nullptr; + /// Exit node. All non-reverting control flow of the function ends here. + /// This node is empty and does not have any exits, but may have multiple entries + /// (e.g. all return statements of the function). + CFGNode* exit = nullptr; + /// Revert node. Control flow of the function in case of revert. + /// This node is empty does not have any exits, but may have multiple entries + /// (e.g. all assert, require, revert and throw statements). + CFGNode* revert = nullptr; +}; + +/** Describes the control flow of a modifier. + * Every placeholder breaks the control flow. The node preceding the + * placeholder is assigned placeholderEntry as exit and the node + * following the placeholder is assigned placeholderExit as entry. + */ +struct ModifierFlow: FunctionFlow +{ + /// Control flow leading towards a placeholder exit in placeholderEntry. + CFGNode* placeholderEntry = nullptr; + /// Control flow coming from a placeholder enter from placeholderExit. + CFGNode* placeholderExit = nullptr; +}; + +class CFG: private ASTConstVisitor +{ +public: + explicit CFG(ErrorReporter& _errorReporter): m_errorReporter(_errorReporter) {} + + bool constructFlow(ASTNode const& _astRoot); + + virtual bool visit(ModifierDefinition const& _modifier) override; + virtual bool visit(FunctionDefinition const& _function) override; + + FunctionFlow const& functionFlow(FunctionDefinition const& _function) const; + + class NodeContainer + { + public: + CFGNode* newNode(); + private: + std::vector<std::unique_ptr<CFGNode>> m_nodes; + }; +private: + /// Initially the control flow for all functions *ignoring* modifiers and for + /// all modifiers is constructed. Afterwards the control flow of functions + /// is adjusted by applying all modifiers. + void applyModifiers(); + + /// Creates a copy of the modifier flow @a _modifierFlow, while replacing the + /// placeholder entry and exit with the function entry and exit, as well as + /// replacing the modifier revert node with the function's revert node. + /// The resulting control flow is the new function flow with the modifier applied. + /// @a _functionFlow is updated in-place. + void applyModifierFlowToFunctionFlow( + ModifierFlow const& _modifierFlow, + FunctionFlow* _functionFlow + ); + + ErrorReporter& m_errorReporter; + + /// Node container. + /// All nodes allocated during the construction of the control flow graph + /// are owned by the CFG class and stored in this container. + NodeContainer m_nodeContainer; + + std::map<FunctionDefinition const*, std::unique_ptr<FunctionFlow>> m_functionControlFlow; + std::map<ModifierDefinition const*, std::unique_ptr<ModifierFlow>> m_modifierControlFlow; +}; + +} +} diff --git a/libsolidity/interface/CompilerStack.cpp b/libsolidity/interface/CompilerStack.cpp index 4ff14aa2..195f806a 100644 --- a/libsolidity/interface/CompilerStack.cpp +++ b/libsolidity/interface/CompilerStack.cpp @@ -29,6 +29,7 @@ #include <libsolidity/ast/AST.h> #include <libsolidity/parsing/Scanner.h> #include <libsolidity/parsing/Parser.h> +#include <libsolidity/analysis/ControlFlowGraph.h> #include <libsolidity/analysis/GlobalContext.h> #include <libsolidity/analysis/NameAndTypeResolver.h> #include <libsolidity/analysis/TypeChecker.h> @@ -224,6 +225,14 @@ bool CompilerStack::analyze() if (noErrors) { + CFG cfg(m_errorReporter); + for (Source const* source: m_sourceOrder) + if (!cfg.constructFlow(*source->ast)) + noErrors = false; + } + + if (noErrors) + { StaticAnalyzer staticAnalyzer(m_errorReporter); for (Source const* source: m_sourceOrder) if (!staticAnalyzer.analyze(*source->ast)) |