1 /*
2  * Cppcheck - A tool for static C/C++ code analysis
3  * Copyright (C) 2007-2021 Cppcheck team.
4  *
5  * This program is free software: you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation, either version 3 of the License, or
8  * (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
17  */
18 
19 //---------------------------------------------------------------------------
20 #ifndef valueflowH
21 #define valueflowH
22 //---------------------------------------------------------------------------
23 
24 #include "astutils.h"
25 #include "config.h"
26 #include "mathlib.h"
27 #include "utils.h"
28 
29 #include <cassert>
30 #include <functional>
31 #include <list>
32 #include <string>
33 #include <type_traits>
34 #include <utility>
35 #include <vector>
36 
37 class ErrorLogger;
38 class Settings;
39 class SymbolDatabase;
40 class Token;
41 class TokenList;
42 class ValueType;
43 class Variable;
44 
45 namespace ValueFlow {
46     struct increment {
47         template<class T>
operatorincrement48         void operator()(T& x) const {
49             x++;
50         }
51     };
52     struct decrement {
53         template<class T>
operatordecrement54         void operator()(T& x) const {
55             x--;
56         }
57     };
58 
59     struct less {
60         template<class T, class U>
operatorless61         bool operator()(const T& x, const U& y) const {
62             return x < y;
63         }
64     };
65 
66     struct adjacent {
67         template<class T, class U>
operatoradjacent68         bool operator()(const T& x, const U& y) const {
69             return std::abs(x - y) == 1;
70         }
71     };
72 
73     struct equalVisitor {
74         template<class T, class U>
operatorequalVisitor75         void operator()(bool& result, T x, U y) const {
76             result = !(x > y || x < y);
77         }
78     };
79     class CPPCHECKLIB Value {
80     public:
81         typedef std::pair<const Token *, std::string> ErrorPathItem;
82         typedef std::list<ErrorPathItem> ErrorPath;
83         enum class Bound { Upper, Lower, Point };
84 
85         explicit Value(long long val = 0, Bound b = Bound::Point)
valueType(ValueType::INT)86             : valueType(ValueType::INT),
87             bound(b),
88             intvalue(val),
89             tokvalue(nullptr),
90             floatValue(0.0),
91             moveKind(MoveKind::NonMovedVariable),
92             varvalue(val),
93             condition(nullptr),
94             varId(0U),
95             safe(false),
96             conditional(false),
97             defaultArg(false),
98             indirect(0),
99             path(0),
100             wideintvalue(val),
101             lifetimeKind(LifetimeKind::Object),
102             lifetimeScope(LifetimeScope::Local),
103             valueKind(ValueKind::Possible)
104         {}
105         Value(const Token* c, long long val, Bound b = Bound::Point);
106 
107         static Value unknown();
108 
equalValue(const ValueFlow::Value & rhs)109         bool equalValue(const ValueFlow::Value& rhs) const {
110             if (valueType != rhs.valueType)
111                 return false;
112             switch (valueType) {
113             case ValueType::INT:
114             case ValueType::CONTAINER_SIZE:
115             case ValueType::BUFFER_SIZE:
116             case ValueType::ITERATOR_START:
117             case ValueType::ITERATOR_END:
118                 if (intvalue != rhs.intvalue)
119                     return false;
120                 break;
121             case ValueType::TOK:
122                 if (tokvalue != rhs.tokvalue)
123                     return false;
124                 break;
125             case ValueType::FLOAT:
126                 // TODO: Write some better comparison
127                 if (floatValue > rhs.floatValue || floatValue < rhs.floatValue)
128                     return false;
129                 break;
130             case ValueType::MOVED:
131                 if (moveKind != rhs.moveKind)
132                     return false;
133                 break;
134             case ValueType::UNINIT:
135                 break;
136             case ValueType::LIFETIME:
137                 if (tokvalue != rhs.tokvalue)
138                     return false;
139                 break;
140             case ValueType::SYMBOLIC:
141                 if (!sameToken(tokvalue, rhs.tokvalue))
142                     return false;
143                 if (intvalue != rhs.intvalue)
144                     return false;
145                 break;
146             }
147             return true;
148         }
149 
150         template<class T, class F>
visitValue(T & self,F f)151         static void visitValue(T& self, F f) {
152             switch (self.valueType) {
153             case ValueType::INT:
154             case ValueType::SYMBOLIC:
155             case ValueType::BUFFER_SIZE:
156             case ValueType::CONTAINER_SIZE:
157             case ValueType::ITERATOR_START:
158             case ValueType::ITERATOR_END: {
159                 f(self.intvalue);
160                 break;
161             }
162             case ValueType::FLOAT: {
163                 f(self.floatValue);
164                 break;
165             }
166             case ValueType::UNINIT:
167             case ValueType::TOK:
168             case ValueType::LIFETIME:
169             case ValueType::MOVED:
170                 break;
171             }
172         }
173 
174         struct compareVisitor {
175             struct innerVisitor {
176                 template<class Compare, class T, class U>
operatorcompareVisitor::innerVisitor177                 void operator()(bool& result, Compare compare, T x, U y) const {
178                     result = compare(x, y);
179                 }
180             };
181             template<class Compare, class T>
operatorcompareVisitor182             void operator()(bool& result, const Value& rhs, Compare compare, T x) const {
183                 visitValue(rhs,
184                            std::bind(innerVisitor{}, std::ref(result), std::move(compare), x, std::placeholders::_1));
185             }
186         };
187 
188         template<class Compare>
compareValue(const Value & rhs,Compare compare)189         bool compareValue(const Value& rhs, Compare compare) const {
190             assert((!this->isSymbolicValue() && !rhs.isSymbolicValue()) ||
191                    (this->valueType == rhs.valueType && sameToken(this->tokvalue, rhs.tokvalue)));
192             bool result = false;
193             visitValue(
194                 *this,
195                 std::bind(compareVisitor{}, std::ref(result), std::ref(rhs), std::move(compare), std::placeholders::_1));
196             return result;
197         }
198 
199         bool operator==(const Value &rhs) const {
200             if (!equalValue(rhs))
201                 return false;
202 
203             return varvalue == rhs.varvalue &&
204                    condition == rhs.condition &&
205                    varId == rhs.varId &&
206                    conditional == rhs.conditional &&
207                    defaultArg == rhs.defaultArg &&
208                    indirect == rhs.indirect &&
209                    valueKind == rhs.valueKind;
210         }
211 
212         bool operator!=(const Value &rhs) const {
213             return !(*this == rhs);
214         }
215 
216         template<class T, REQUIRES("T must be an arithmetic type", std::is_arithmetic<T> )>
equalTo(const T & x)217         bool equalTo(const T& x) const {
218             bool result = false;
219             visitValue(*this, std::bind(equalVisitor{}, std::ref(result), x, std::placeholders::_1));
220             return result;
221         }
222 
decreaseRange()223         void decreaseRange() {
224             if (bound == Bound::Lower)
225                 visitValue(*this, increment{});
226             else if (bound == Bound::Upper)
227                 visitValue(*this, decrement{});
228         }
229 
invertBound()230         void invertBound() {
231             if (bound == Bound::Lower)
232                 bound = Bound::Upper;
233             else if (bound == Bound::Upper)
234                 bound = Bound::Lower;
235         }
236 
invertRange()237         void invertRange() {
238             invertBound();
239             decreaseRange();
240         }
241 
242         void assumeCondition(const Token* tok);
243 
244         std::string infoString() const;
245 
246         enum class ValueType {
247             INT,
248             TOK,
249             FLOAT,
250             MOVED,
251             UNINIT,
252             CONTAINER_SIZE,
253             LIFETIME,
254             BUFFER_SIZE,
255             ITERATOR_START,
256             ITERATOR_END,
257             SYMBOLIC
258         } valueType;
isIntValue()259         bool isIntValue() const {
260             return valueType == ValueType::INT;
261         }
isTokValue()262         bool isTokValue() const {
263             return valueType == ValueType::TOK;
264         }
isFloatValue()265         bool isFloatValue() const {
266             return valueType == ValueType::FLOAT;
267         }
isMovedValue()268         bool isMovedValue() const {
269             return valueType == ValueType::MOVED;
270         }
isUninitValue()271         bool isUninitValue() const {
272             return valueType == ValueType::UNINIT;
273         }
isContainerSizeValue()274         bool isContainerSizeValue() const {
275             return valueType == ValueType::CONTAINER_SIZE;
276         }
isLifetimeValue()277         bool isLifetimeValue() const {
278             return valueType == ValueType::LIFETIME;
279         }
isBufferSizeValue()280         bool isBufferSizeValue() const {
281             return valueType == ValueType::BUFFER_SIZE;
282         }
isIteratorValue()283         bool isIteratorValue() const {
284             return valueType == ValueType::ITERATOR_START || valueType == ValueType::ITERATOR_END;
285         }
isIteratorStartValue()286         bool isIteratorStartValue() const {
287             return valueType == ValueType::ITERATOR_START;
288         }
isIteratorEndValue()289         bool isIteratorEndValue() const {
290             return valueType == ValueType::ITERATOR_END;
291         }
isSymbolicValue()292         bool isSymbolicValue() const {
293             return valueType == ValueType::SYMBOLIC;
294         }
295 
isLocalLifetimeValue()296         bool isLocalLifetimeValue() const {
297             return valueType == ValueType::LIFETIME && lifetimeScope == LifetimeScope::Local;
298         }
299 
isArgumentLifetimeValue()300         bool isArgumentLifetimeValue() const {
301             return valueType == ValueType::LIFETIME && lifetimeScope == LifetimeScope::Argument;
302         }
303 
isSubFunctionLifetimeValue()304         bool isSubFunctionLifetimeValue() const {
305             return valueType == ValueType::LIFETIME && lifetimeScope == LifetimeScope::SubFunction;
306         }
307 
isNonValue()308         bool isNonValue() const {
309             return isMovedValue() || isUninitValue() || isLifetimeValue();
310         }
311 
312         /** The value bound  */
313         Bound bound;
314 
315         /** int value (or sometimes bool value?) */
316         long long intvalue;
317 
318         /** token value - the token that has the value. this is used for pointer aliases, strings, etc. */
319         const Token *tokvalue;
320 
321         /** float value */
322         double floatValue;
323 
324         /** kind of moved  */
325         enum class MoveKind {NonMovedVariable, MovedVariable, ForwardedVariable} moveKind;
326 
327         /** For calculated values - variable value that calculated value depends on */
328         long long varvalue;
329 
330         /** Condition that this value depends on */
331         const Token *condition;
332 
333         ErrorPath errorPath;
334 
335         /** For calculated values - varId that calculated value depends on */
336         nonneg int varId;
337 
338         /** value relies on safe checking */
339         bool safe;
340 
341         /** Conditional value */
342         bool conditional;
343 
344         /** Is this value passed as default parameter to the function? */
345         bool defaultArg;
346 
347         int indirect;
348 
349         /** Path id */
350         MathLib::bigint path;
351 
352         /** int value before implicit truncation */
353         long long wideintvalue;
354 
355         enum class LifetimeKind {
356             // Pointer points to a member of lifetime
357             Object,
358             // A member of object points to the lifetime
359             SubObject,
360             // Lambda has captured lifetime(similar to SubObject)
361             Lambda,
362             // Iterator points to the lifetime of a container(similar to Object)
363             Iterator,
364             // A pointer that holds the address of the lifetime
365             Address
366         } lifetimeKind;
367 
368         enum class LifetimeScope { Local, Argument, SubFunction } lifetimeScope;
369 
370         static const char* toString(MoveKind moveKind);
371         static const char* toString(LifetimeKind lifetimeKind);
372         static const char* toString(LifetimeScope lifetimeScope);
373         static const char* toString(Bound bound);
374 
375         /** How known is this value */
376         enum class ValueKind {
377             /** This value is possible, other unlisted values may also be possible */
378             Possible,
379             /** Only listed values are possible */
380             Known,
381             /** Inconclusive */
382             Inconclusive,
383             /** Listed values are impossible */
384             Impossible
385         } valueKind;
386 
setKnown()387         void setKnown() {
388             valueKind = ValueKind::Known;
389         }
390 
isKnown()391         bool isKnown() const {
392             return valueKind == ValueKind::Known;
393         }
394 
setPossible()395         void setPossible() {
396             valueKind = ValueKind::Possible;
397         }
398 
isPossible()399         bool isPossible() const {
400             return valueKind == ValueKind::Possible;
401         }
402 
isImpossible()403         bool isImpossible() const {
404             return valueKind == ValueKind::Impossible;
405         }
406 
setImpossible()407         void setImpossible() {
408             valueKind = ValueKind::Impossible;
409         }
410 
411         void setInconclusive(bool inconclusive = true) {
412             if (inconclusive)
413                 valueKind = ValueKind::Inconclusive;
414         }
415 
isInconclusive()416         bool isInconclusive() const {
417             return valueKind == ValueKind::Inconclusive;
418         }
419 
changeKnownToPossible()420         void changeKnownToPossible() {
421             if (isKnown())
422                 valueKind = ValueKind::Possible;
423         }
424 
errorSeverity()425         bool errorSeverity() const {
426             return !condition && !defaultArg;
427         }
428 
429         static bool sameToken(const Token* tok1, const Token* tok2);
430     };
431 
432     /// Constant folding of expression. This can be used before the full ValueFlow has been executed (ValueFlow::setValues).
433     const ValueFlow::Value * valueFlowConstantFoldAST(Token *expr, const Settings *settings);
434 
435     /// Perform valueflow analysis.
436     void setValues(TokenList *tokenlist, SymbolDatabase* symboldatabase, ErrorLogger *errorLogger, const Settings *settings);
437 
438     std::string eitherTheConditionIsRedundant(const Token *condition);
439 
440     size_t getSizeOf(const ValueType &vt, const Settings *settings);
441 
442     const ValueFlow::Value* findValue(const std::list<ValueFlow::Value>& values,
443                                       const Settings* settings,
444                                       std::function<bool(const ValueFlow::Value&)> pred);
445 
446     std::vector<ValueFlow::Value> isOutOfBounds(const Value& size, const Token* indexTok, bool possible = true);
447 }
448 
449 struct LifetimeToken {
450     const Token* token;
451     bool addressOf;
452     ValueFlow::Value::ErrorPath errorPath;
453     bool inconclusive;
454 
LifetimeTokenLifetimeToken455     LifetimeToken() : token(nullptr), addressOf(false), errorPath(), inconclusive(false) {}
456 
LifetimeTokenLifetimeToken457     LifetimeToken(const Token* token, ValueFlow::Value::ErrorPath errorPath)
458         : token(token), addressOf(false), errorPath(std::move(errorPath)), inconclusive(false)
459     {}
460 
LifetimeTokenLifetimeToken461     LifetimeToken(const Token* token, bool addressOf, ValueFlow::Value::ErrorPath errorPath)
462         : token(token), addressOf(addressOf), errorPath(std::move(errorPath)), inconclusive(false)
463     {}
464 
setAddressOfLifetimeToken465     static std::vector<LifetimeToken> setAddressOf(std::vector<LifetimeToken> v, bool b) {
466         for (LifetimeToken& x : v)
467             x.addressOf = b;
468         return v;
469     }
470 
setInconclusiveLifetimeToken471     static std::vector<LifetimeToken> setInconclusive(std::vector<LifetimeToken> v, bool b) {
472         for (LifetimeToken& x : v)
473             x.inconclusive = b;
474         return v;
475     }
476 };
477 
478 const Token *parseCompareInt(const Token *tok, ValueFlow::Value &true_value, ValueFlow::Value &false_value, const std::function<std::vector<MathLib::bigint>(const Token*)>& evaluate);
479 const Token *parseCompareInt(const Token *tok, ValueFlow::Value &true_value, ValueFlow::Value &false_value);
480 
481 ValueFlow::Value inferCondition(std::string op, MathLib::bigint val, const Token* varTok);
482 ValueFlow::Value inferCondition(const std::string& op, const Token* varTok, MathLib::bigint val);
483 
484 std::vector<LifetimeToken> getLifetimeTokens(const Token* tok,
485                                              bool escape = false,
486                                              ValueFlow::Value::ErrorPath errorPath = ValueFlow::Value::ErrorPath{});
487 
488 bool hasLifetimeToken(const Token* tok, const Token* lifetime);
489 
490 const Variable* getLifetimeVariable(const Token* tok, ValueFlow::Value::ErrorPath& errorPath, bool* addressOf = nullptr);
491 
492 const Variable* getLifetimeVariable(const Token* tok);
493 
494 bool isLifetimeBorrowed(const Token *tok, const Settings *settings);
495 
496 std::string lifetimeType(const Token *tok, const ValueFlow::Value *val);
497 
498 std::string lifetimeMessage(const Token *tok, const ValueFlow::Value *val, ValueFlow::Value::ErrorPath &errorPath);
499 
500 CPPCHECKLIB ValueFlow::Value getLifetimeObjValue(const Token *tok, bool inconclusive = false);
501 
502 CPPCHECKLIB std::vector<ValueFlow::Value> getLifetimeObjValues(const Token *tok, bool inconclusive = false, bool subfunction = false);
503 
504 #endif // valueflowH
505