#include "astutils.h"

#include "config.h"

#include "errortypes.h"

#include "findtoken.h"

#include "infer.h"

#include "library.h"

#include "mathlib.h"

#include "settings.h"

#include "symboldatabase.h"

#include "token.h"

#include "utils.h"

#include "valueflow.h"

#include "valueptr.h"

#include "vfvalue.h"

#include "checkclass.h"

#include <algorithm>

#include <cstring>

#include <functional>

#include <initializer_list>

#include <iterator>

#include <list>

#include <set>

#include <type_traits>

#include <unordered_map>

#include <utility>

const Token* findExpression(const nonneg int exprid,

const Token* start,

const Token* end,

const std::function<bool(const Token*)>& pred)

{

if (exprid == 0)

return nullptr;

if (!precedes(start, end))

return nullptr;

for (const Token* tok = start; tok != end; tok = tok->next()) {

if (tok->exprId() != exprid)

continue;

if (pred(tok))

return tok;

}

return nullptr;

}

static int findArgumentPosRecursive(const Token* tok, const Token* tokToFind, bool &found, nonneg int depth=0)

}

static int findArgumentPos(const Token* tok, const Token* tokToFind){

}

static int getArgumentPos(const Token* ftok, const Token* tokToFind){

}

template<class T, class OuputIterator, REQUIRES("T must be a Token class", std::is_convertible<T*, const Token*> )>

static void astFlattenCopy(T* tok, const char* op, OuputIterator out, int depth = 100)

}

std::vector<const Token*> astFlatten(const Token* tok, const char* op)

}

std::vector<Token*> astFlatten(Token* tok, const char* op)

}

nonneg int astCount(const Token* tok, const char* op, int depth)

}

bool astHasToken(const Token* root, const Token * tok)

}

bool astHasVar(const Token * tok, nonneg int varid)

}

bool astHasExpr(const Token* tok, nonneg int exprid)

}

static bool astIsCharWithSign(const Token *tok, ValueType::Sign sign)

}

bool astIsSignedChar(const Token *tok)

{

return astIsCharWithSign(tok, ValueType::Sign::SIGNED);

}

bool astIsUnknownSignChar(const Token *tok)

{

return astIsCharWithSign(tok, ValueType::Sign::UNKNOWN_SIGN);

}

bool astIsGenericChar(const Token* tok)

{

return !astIsPointer(tok) && tok && tok->valueType() && (tok->valueType()->type == ValueType::Type::CHAR || tok->valueType()->type == ValueType::Type::WCHAR_T);

}

bool astIsPrimitive(const Token* tok)

}

bool astIsIntegral(const Token *tok, bool unknown)

}

bool astIsUnsigned(const Token* tok)

{

return tok && tok->valueType() && tok->valueType()->sign == ValueType::UNSIGNED;

}

bool astIsFloat(const Token *tok, bool unknown)

}

bool astIsBool(const Token *tok)

{

return tok && (tok->isBoolean() || (tok->valueType() && tok->valueType()->type == ValueType::Type::BOOL && !tok->valueType()->pointer));

}

bool astIsPointer(const Token *tok)

{

return tok && tok->valueType() && tok->valueType()->pointer;

}

bool astIsSmartPointer(const Token* tok)

{

return tok && tok->valueType() && tok->valueType()->smartPointerTypeToken;

}

bool astIsUniqueSmartPointer(const Token* tok)

}

bool astIsIterator(const Token *tok)

{

return tok && tok->valueType() && tok->valueType()->type == ValueType::Type::ITERATOR;

}

bool astIsContainer(const Token* tok) {

return getLibraryContainer(tok) != nullptr && !astIsIterator(tok);

}

bool astIsNonStringContainer(const Token* tok)

}

bool astIsContainerView(const Token* tok)

}

bool astIsContainerOwned(const Token* tok) {

return astIsContainer(tok) && !astIsContainerView(tok);

}

bool astIsContainerString(const Token* tok)

}

static std::pair<const Token*, const Library::Container*> getContainerFunction(const Token* tok, const Library& library)

}

Library::Container::Action astContainerAction(const Token* tok, const Library& library, const Token** ftok)

}

Library::Container::Yield astContainerYield(const Token* tok, const Library& library, const Token** ftok)

}

Library::Container::Yield astFunctionYield(const Token* tok, const Settings& settings, const Token** ftok)

}

bool astIsRangeBasedForDecl(const Token* tok)

{

return Token::simpleMatch(tok->astParent(), ":") && Token::simpleMatch(tok->astParent()->astParent(), "(");

}

std::string astCanonicalType(const Token *expr, bool pointedToType)

}

static bool match(const Token *tok, const std::string &rhs)

}

const Token * astIsVariableComparison(const Token *tok, const std::string &comp, const std::string &rhs, const Token **vartok)

{

if (!tok)

return nullptr;

const Token *ret = nullptr;

if (tok->isComparisonOp()) {

if (tok->astOperand1() && match(tok->astOperand1(), rhs)) {

// Invert comparator

std::string s = tok->str();

if (s[0] == '>')

s[0] = '<';

else if (s[0] == '<')

s[0] = '>';

if (s == comp) {

ret = tok->astOperand2();

}

} else if (tok->str() == comp && tok->astOperand2() && match(tok->astOperand2(), rhs)) {

ret = tok->astOperand1();

}

} else if (comp == "!=" && rhs == "0") {

if (tok->str() == "!") {

ret = tok->astOperand1();

// handle (!(x==0)) as (x!=0)

astIsVariableComparison(ret, "==", "0", &ret);

} else

ret = tok;

} else if (comp == "==" && rhs == "0") {

if (tok->str() == "!") {

ret = tok->astOperand1();

// handle (!(x!=0)) as (x==0)

astIsVariableComparison(ret, "!=", "0", &ret);

}

}

while (ret && ret->str() == ".")

ret = ret->astOperand2();

if (ret && ret->str() == "=" && ret->astOperand1() && ret->astOperand1()->varId())

ret = ret->astOperand1();

else if (ret && ret->varId() == 0U)

ret = nullptr;

if (vartok)

*vartok = ret;

return ret;

}

bool isVariableDecl(const Token* tok)

}

bool isStlStringType(const Token* tok)

}

bool isVoidCast(const Token* tok)

}

bool isTemporary(const Token* tok, const Library* library, bool unknown)

}

static bool isFunctionCall(const Token* tok)

}

static bool hasToken(const Token * startTok, const Token * stopTok, const Token * tok)

}

template<class T, REQUIRES("T must be a Token class", std::is_convertible<T*, const Token*> )>

static T* previousBeforeAstLeftmostLeafGeneric(T* tok)

{

if (!tok)

return nullptr;

T* leftmostLeaf = tok;

while (leftmostLeaf->astOperand1())

leftmostLeaf = leftmostLeaf->astOperand1();

return leftmostLeaf->previous();

}

const Token* previousBeforeAstLeftmostLeaf(const Token* tok)

{

return previousBeforeAstLeftmostLeafGeneric(tok);

}

Token* previousBeforeAstLeftmostLeaf(Token* tok)

{

return previousBeforeAstLeftmostLeafGeneric(tok);

}

template<class T, REQUIRES("T must be a Token class", std::is_convertible<T*, const Token*> )>

static T* nextAfterAstRightmostLeafGeneric(T* tok)

{

T * rightmostLeaf = tok;

if (!rightmostLeaf || !rightmostLeaf->astOperand1())

return nullptr;

do {

if (T* lam = findLambdaEndToken(rightmostLeaf)) {

rightmostLeaf = lam;

break;

}

if (rightmostLeaf->astOperand2() && precedes(rightmostLeaf, rightmostLeaf->astOperand2()))

rightmostLeaf = rightmostLeaf->astOperand2();

else if (rightmostLeaf->astOperand1() && precedes(rightmostLeaf, rightmostLeaf->astOperand1()))

rightmostLeaf = rightmostLeaf->astOperand1();

else

break;

} while (rightmostLeaf->astOperand1() || rightmostLeaf->astOperand2());

while (Token::Match(rightmostLeaf->next(), "]|)") && !hasToken(rightmostLeaf->linkAt(1), rightmostLeaf->next(), tok))

rightmostLeaf = rightmostLeaf->next();

if (Token::Match(rightmostLeaf, "{|(|[") && rightmostLeaf->link())

rightmostLeaf = rightmostLeaf->link();

return rightmostLeaf->next();

}

const Token* nextAfterAstRightmostLeaf(const Token* tok)

{

return nextAfterAstRightmostLeafGeneric(tok);

}

Token* nextAfterAstRightmostLeaf(Token* tok)

{

return nextAfterAstRightmostLeafGeneric(tok);

}

const Token* astParentSkipParens(const Token* tok)

{

return astParentSkipParens(const_cast<Token*>(tok));

}

Token* astParentSkipParens(Token* tok)

{

if (!tok)

return nullptr;

Token * parent = tok->astParent();

if (!Token::simpleMatch(parent, "("))

return parent;

if (parent->link() != nextAfterAstRightmostLeaf(tok))

return parent;

if (Token::Match(parent->previous(), "%name% (") ||

(Token::simpleMatch(parent->previous(), "> (") && parent->linkAt(-1)))

return parent;

return astParentSkipParens(parent);

}

const Token* getParentMember(const Token * tok)

{

if (!tok)

return tok;

const Token * parent = tok->astParent();

if (!Token::simpleMatch(parent, "."))

return tok;

if (astIsRHS(tok)) {

if (Token::simpleMatch(parent->astOperand1(), "."))

return parent->astOperand1()->astOperand2();

return parent->astOperand1();

}

const Token * gparent = parent->astParent();

if (!Token::simpleMatch(gparent, ".") || gparent->astOperand2() != parent)

return tok;

if (gparent->astOperand1())

return gparent->astOperand1();

return tok;

}

const Token* getParentLifetime(const Token* tok)

{

if (!tok)

return tok;

// Skipping checking for variable if its a pointer-to-member

if (!Token::simpleMatch(tok->previous(), ". *")) {

const Variable* var = tok->variable();

// TODO: Call getLifetimeVariable for deeper analysis

if (!var)

return tok;

if (var->isLocal() || var->isArgument())

return tok;

}

const Token* parent = getParentMember(tok);

if (parent != tok)

return getParentLifetime(parent);

return tok;

}

static std::vector<const Token*> getParentMembers(const Token* tok)

}

static const Token* getParentLifetimeObject(const Token* tok)

{

while (Token::simpleMatch(tok, "["))

tok = tok->astOperand1();

return tok;

}

const Token* getParentLifetime(const Token* tok, const Library& library)

{

std::vector<const Token*> members = getParentMembers(tok);

if (members.size() < 2)

return tok;

// Find the first local variable, temporary, or array

auto it = std::find_if(members.crbegin(), members.crend(), [&](const Token* tok2) {

const Variable* var = tok2->variable();

if (var)

return var->isLocal() || var->isArgument();

if (Token::simpleMatch(tok2, "["))

return true;

return isTemporary(tok2, &library);

});

if (it == members.rend())

return tok;

// If any of the submembers are borrowed types then stop

if (std::any_of(it.base() - 1, members.cend() - 1, [&](const Token* tok2) {

const Token* obj = getParentLifetimeObject(tok2);

if (!obj)

return false;

const Variable* var = obj->variable();

// Check for arrays first since astIsPointer will return true, but an array is not a borrowed type

if (var && var->isArray())

return false;

if (astIsPointer(obj) || astIsContainerView(obj) || astIsIterator(obj))

return true;

if (!astIsUniqueSmartPointer(obj)) {

if (astIsSmartPointer(obj))

return true;

const Token* dotTok = obj->next();

if (!Token::simpleMatch(dotTok, ".")) {

const Token* endTok = nextAfterAstRightmostLeaf(obj);

if (!endTok)

dotTok = obj->next();

else if (Token::simpleMatch(endTok, "."))

dotTok = endTok;

else if (Token::simpleMatch(endTok->next(), "."))

dotTok = endTok->next();

}

// If we are dereferencing the member variable then treat it as borrowed

if (Token::simpleMatch(dotTok, ".") && dotTok->originalName() == "->")

return true;

}

return var && var->isReference();

}))

return nullptr;

const Token* result = getParentLifetimeObject(*it);

if (result != *it)

return getParentLifetime(result);

return result;

}

static bool isInConstructorList(const Token* tok)

}

std::vector<ValueType> getParentValueTypes(const Token* tok, const Settings& settings, const Token** parent)

}

bool astIsLHS(const Token* tok)

}

bool astIsRHS(const Token* tok)

}

template<class T, REQUIRES("T must be a Token class", std::is_convertible<T*, const Token*> )>

static T* getCondTokImpl(T* tok)

{

if (!tok)

return nullptr;

if (Token::simpleMatch(tok, "("))

return getCondTok(tok->previous());

if (Token::simpleMatch(tok, "do {")) {

T* endTok = tok->linkAt(1);

if (Token::simpleMatch(endTok, "} while ("))

return endTok->tokAt(2)->astOperand2();

}

if (Token::simpleMatch(tok, "for") && Token::simpleMatch(tok->next()->astOperand2(), ";") &&

tok->next()->astOperand2()->astOperand2())

return tok->next()->astOperand2()->astOperand2()->astOperand1();

if (Token::simpleMatch(tok->next()->astOperand2(), ";"))

return tok->next()->astOperand2()->astOperand1();

if (tok->isName() && !tok->isControlFlowKeyword())

return nullptr;

return tok->next()->astOperand2();

}

template<class T, REQUIRES("T must be a Token class", std::is_convertible<T*, const Token*> )>

static T* getCondTokFromEndImpl(T* endBlock)

{

if (!Token::simpleMatch(endBlock, "}"))

return nullptr;

T* startBlock = endBlock->link();

if (!Token::simpleMatch(startBlock, "{"))

return nullptr;

if (Token::simpleMatch(startBlock->previous(), "do"))

return getCondTok(startBlock->previous());

if (Token::simpleMatch(startBlock->previous(), ")"))

return getCondTok(startBlock->linkAt(-1));

if (Token::simpleMatch(startBlock->tokAt(-2), "} else {"))

return getCondTokFromEnd(startBlock->tokAt(-2));

return nullptr;

}

template<class T, REQUIRES("T must be a Token class", std::is_convertible<T*, const Token*> )>

static T* getInitTokImpl(T* tok)

{

if (!tok)

return nullptr;

if (Token::Match(tok, "%name% ("))

return getInitTokImpl(tok->next());

if (tok->str() != "(")

return nullptr;

if (!Token::simpleMatch(tok->astOperand2(), ";"))

return nullptr;

if (Token::simpleMatch(tok->astOperand2()->astOperand1(), ";"))

return nullptr;

return tok->astOperand2()->astOperand1();

}

template<class T, REQUIRES("T must be a Token class", std::is_convertible<T*, const Token*> )>

static T* getStepTokImpl(T* tok)

{

if (!tok)

return nullptr;

if (Token::Match(tok, "%name% ("))

return getStepTokImpl(tok->next());

if (tok->str() != "(")

return nullptr;

if (!Token::simpleMatch(tok->astOperand2(), ";"))

return nullptr;

if (!Token::simpleMatch(tok->astOperand2()->astOperand2(), ";"))

return nullptr;

return tok->astOperand2()->astOperand2()->astOperand2();

}

Token* getCondTok(Token* tok)

{

return getCondTokImpl(tok);

}

const Token* getCondTok(const Token* tok)

{

return getCondTokImpl(tok);

}

Token* getCondTokFromEnd(Token* endBlock)

{

return getCondTokFromEndImpl(endBlock);

}

const Token* getCondTokFromEnd(const Token* endBlock)

{

return getCondTokFromEndImpl(endBlock);

}

Token* getInitTok(Token* tok) {

return getInitTokImpl(tok);

}

const Token* getInitTok(const Token* tok) {

return getInitTokImpl(tok);

}

Token* getStepTok(Token* tok) {

return getStepTokImpl(tok);

}

const Token* getStepTok(const Token* tok) {

return getStepTokImpl(tok);

}

const Token *findNextTokenFromBreak(const Token *breakToken)

{

const Scope *scope = breakToken->scope();

while (scope) {

if (scope->isLoopScope() || scope->type == ScopeType::eSwitch) {

if (scope->type == ScopeType::eDo && Token::simpleMatch(scope->bodyEnd, "} while ("))

return scope->bodyEnd->linkAt(2)->next();

return scope->bodyEnd;

}

scope = scope->nestedIn;

}

return nullptr;

}

bool extractForLoopValues(const Token *forToken,