aboutsummaryrefslogtreecommitdiffstats
path: root/libsolidity/analysis/ControlFlowGraph.h
blob: 8fe9fe8ee03b2a50a042b2dc43850cb43be419f2 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
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 <liblangutil/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(langutil::ErrorReporter& _errorReporter): m_errorReporter(_errorReporter) {}

    bool constructFlow(ASTNode const& _astRoot);

    bool visit(ModifierDefinition const& _modifier) override;
    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
    );

    langutil::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;
};

}
}