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