1 /*
2 This file is part of solidity.
3
4 solidity is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 solidity is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with solidity. If not, see <http://www.gnu.org/licenses/>.
16 */
17 // SPDX-License-Identifier: GPL-3.0
18
19 #include <libsolidity/analysis/ControlFlowAnalyzer.h>
20
21 #include <liblangutil/SourceLocation.h>
22 #include <libsolutil/Algorithms.h>
23
24 #include <range/v3/algorithm/sort.hpp>
25
26 #include <functional>
27
28 using namespace std;
29 using namespace std::placeholders;
30 using namespace solidity::langutil;
31 using namespace solidity::frontend;
32
33
run()34 bool ControlFlowAnalyzer::run()
35 {
36 for (auto& [pair, flow]: m_cfg.allFunctionFlows())
37 analyze(*pair.function, pair.contract, *flow);
38
39 return !Error::containsErrors(m_errorReporter.errors());
40 }
41
analyze(FunctionDefinition const & _function,ContractDefinition const * _contract,FunctionFlow const & _flow)42 void ControlFlowAnalyzer::analyze(FunctionDefinition const& _function, ContractDefinition const* _contract, FunctionFlow const& _flow)
43 {
44 if (!_function.isImplemented())
45 return;
46
47 optional<string> mostDerivedContractName;
48
49 // The name of the most derived contract only required if it differs from
50 // the functions contract
51 if (_contract && _contract != _function.annotation().contract)
52 mostDerivedContractName = _contract->name();
53
54 checkUninitializedAccess(
55 _flow.entry,
56 _flow.exit,
57 _function.body().statements().empty(),
58 mostDerivedContractName
59 );
60 checkUnreachable(_flow.entry, _flow.exit, _flow.revert, _flow.transactionReturn);
61 }
62
63
checkUninitializedAccess(CFGNode const * _entry,CFGNode const * _exit,bool _emptyBody,optional<string> _contractName)64 void ControlFlowAnalyzer::checkUninitializedAccess(CFGNode const* _entry, CFGNode const* _exit, bool _emptyBody, optional<string> _contractName)
65 {
66 struct NodeInfo
67 {
68 set<VariableDeclaration const*> unassignedVariablesAtEntry;
69 set<VariableDeclaration const*> unassignedVariablesAtExit;
70 set<VariableOccurrence const*> uninitializedVariableAccesses;
71 /// Propagate the information from another node to this node.
72 /// To be used to propagate information from a node to its exit nodes.
73 /// Returns true, if new variables were added and thus the current node has
74 /// to be traversed again.
75 bool propagateFrom(NodeInfo const& _entryNode)
76 {
77 size_t previousUnassignedVariablesAtEntry = unassignedVariablesAtEntry.size();
78 size_t previousUninitializedVariableAccessess = uninitializedVariableAccesses.size();
79 unassignedVariablesAtEntry += _entryNode.unassignedVariablesAtExit;
80 uninitializedVariableAccesses += _entryNode.uninitializedVariableAccesses;
81 return
82 unassignedVariablesAtEntry.size() > previousUnassignedVariablesAtEntry ||
83 uninitializedVariableAccesses.size() > previousUninitializedVariableAccessess
84 ;
85 }
86 };
87 map<CFGNode const*, NodeInfo> nodeInfos;
88 set<CFGNode const*> nodesToTraverse;
89 nodesToTraverse.insert(_entry);
90
91 // Walk all paths starting from the nodes in ``nodesToTraverse`` until ``NodeInfo::propagateFrom``
92 // returns false for all exits, i.e. until all paths have been walked with maximal sets of unassigned
93 // variables and accesses.
94 while (!nodesToTraverse.empty())
95 {
96 CFGNode const* currentNode = *nodesToTraverse.begin();
97 nodesToTraverse.erase(nodesToTraverse.begin());
98
99 auto& nodeInfo = nodeInfos[currentNode];
100 auto unassignedVariables = nodeInfo.unassignedVariablesAtEntry;
101 for (auto const& variableOccurrence: currentNode->variableOccurrences)
102 {
103 switch (variableOccurrence.kind())
104 {
105 case VariableOccurrence::Kind::Assignment:
106 unassignedVariables.erase(&variableOccurrence.declaration());
107 break;
108 case VariableOccurrence::Kind::InlineAssembly:
109 // We consider all variables referenced in inline assembly as accessed.
110 // So far any reference is enough, but we might want to actually analyze
111 // the control flow in the assembly at some point.
112 case VariableOccurrence::Kind::Access:
113 case VariableOccurrence::Kind::Return:
114 if (unassignedVariables.count(&variableOccurrence.declaration()))
115 {
116 // Merely store the unassigned access. We do not generate an error right away, since this
117 // path might still always revert. It is only an error if this is propagated to the exit
118 // node of the function (i.e. there is a path with an uninitialized access).
119 nodeInfo.uninitializedVariableAccesses.insert(&variableOccurrence);
120 }
121 break;
122 case VariableOccurrence::Kind::Declaration:
123 unassignedVariables.insert(&variableOccurrence.declaration());
124 break;
125 }
126 }
127 nodeInfo.unassignedVariablesAtExit = std::move(unassignedVariables);
128
129 // Propagate changes to all exits and queue them for traversal, if needed.
130 for (auto const& exit: currentNode->exits)
131 if (
132 auto exists = valueOrNullptr(nodeInfos, exit);
133 nodeInfos[exit].propagateFrom(nodeInfo) || !exists
134 )
135 nodesToTraverse.insert(exit);
136 }
137
138 auto const& exitInfo = nodeInfos[_exit];
139 if (!exitInfo.uninitializedVariableAccesses.empty())
140 {
141 vector<VariableOccurrence const*> uninitializedAccessesOrdered(
142 exitInfo.uninitializedVariableAccesses.begin(),
143 exitInfo.uninitializedVariableAccesses.end()
144 );
145 ranges::sort(
146 uninitializedAccessesOrdered,
147 [](VariableOccurrence const* lhs, VariableOccurrence const* rhs) -> bool
148 {
149 return *lhs < *rhs;
150 }
151 );
152
153 for (auto const* variableOccurrence: uninitializedAccessesOrdered)
154 {
155 VariableDeclaration const& varDecl = variableOccurrence->declaration();
156
157 SecondarySourceLocation ssl;
158 if (variableOccurrence->occurrence())
159 ssl.append("The variable was declared here.", varDecl.location());
160
161 bool isStorage = varDecl.type()->dataStoredIn(DataLocation::Storage);
162 bool isCalldata = varDecl.type()->dataStoredIn(DataLocation::CallData);
163 if (isStorage || isCalldata)
164 m_errorReporter.typeError(
165 3464_error,
166 variableOccurrence->occurrence() ?
167 *variableOccurrence->occurrence() :
168 varDecl.location(),
169 ssl,
170 "This variable is of " +
171 string(isStorage ? "storage" : "calldata") +
172 " pointer type and can be " +
173 (variableOccurrence->kind() == VariableOccurrence::Kind::Return ? "returned" : "accessed") +
174 " without prior assignment, which would lead to undefined behaviour."
175 );
176 else if (!_emptyBody && varDecl.name().empty())
177 {
178 if (!m_unassignedReturnVarsAlreadyWarnedFor.emplace(&varDecl).second)
179 continue;
180
181 m_errorReporter.warning(
182 6321_error,
183 varDecl.location(),
184 "Unnamed return variable can remain unassigned" +
185 (
186 _contractName.has_value() ?
187 " when the function is called when \"" + _contractName.value() + "\" is the most derived contract." :
188 "."
189 ) +
190 " Add an explicit return with value to all non-reverting code paths or name the variable."
191 );
192 }
193 }
194 }
195 }
196
checkUnreachable(CFGNode const * _entry,CFGNode const * _exit,CFGNode const * _revert,CFGNode const * _transactionReturn)197 void ControlFlowAnalyzer::checkUnreachable(CFGNode const* _entry, CFGNode const* _exit, CFGNode const* _revert, CFGNode const* _transactionReturn)
198 {
199 // collect all nodes reachable from the entry point
200 std::set<CFGNode const*> reachable = util::BreadthFirstSearch<CFGNode const*>{{_entry}}.run(
201 [](CFGNode const* _node, auto&& _addChild) {
202 for (CFGNode const* exit: _node->exits)
203 _addChild(exit);
204 }
205 ).visited;
206
207 // traverse all paths backwards from exit, revert and transaction return
208 // and extract (valid) source locations of unreachable nodes into sorted set
209 std::set<SourceLocation> unreachable;
210 util::BreadthFirstSearch<CFGNode const*>{{_exit, _revert, _transactionReturn}}.run(
211 [&](CFGNode const* _node, auto&& _addChild) {
212 if (!reachable.count(_node) && _node->location.isValid())
213 unreachable.insert(_node->location);
214 for (CFGNode const* entry: _node->entries)
215 _addChild(entry);
216 }
217 );
218
219 for (auto it = unreachable.begin(); it != unreachable.end();)
220 {
221 SourceLocation location = *it++;
222 // Extend the location, as long as the next location overlaps (unreachable is sorted).
223 for (; it != unreachable.end() && it->start <= location.end; ++it)
224 location.end = std::max(location.end, it->end);
225
226 if (m_unreachableLocationsAlreadyWarnedFor.emplace(location).second)
227 m_errorReporter.warning(5740_error, location, "Unreachable code.");
228 }
229 }
230