Line data Source code
1 : /*
2 : * Cppcheck - A tool for static C/C++ code analysis
3 : * Copyright (C) 2007-2024 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 : #ifndef GUARD_PROGRAMMEMORY_H
20 : #define GUARD_PROGRAMMEMORY_H
21 :
22 : #include "config.h"
23 : #include "mathlib.h"
24 : #include "vfvalue.h" // needed for alias
25 :
26 : #include <cstddef>
27 : #include <functional>
28 : #include <map>
29 : #include <string>
30 : #include <unordered_map>
31 : #include <utility>
32 : #include <vector>
33 :
34 : class Scope;
35 : class Token;
36 : class Settings;
37 :
38 : // Class used to handle heterogeneous lookup in unordered_map(since we can't use C++20 yet)
39 : struct ExprIdToken {
40 : const Token* tok = nullptr;
41 : nonneg int exprid = 0;
42 :
43 : ExprIdToken() = default;
44 : // cppcheck-suppress noExplicitConstructor
45 : // NOLINTNEXTLINE(google-explicit-constructor)
46 : ExprIdToken(const Token* tok);
47 : // TODO: Make this constructor only available from ProgramMemory
48 : // cppcheck-suppress noExplicitConstructor
49 : // NOLINTNEXTLINE(google-explicit-constructor)
50 3422050 : ExprIdToken(nonneg int exprid) : exprid(exprid) {}
51 :
52 : nonneg int getExpressionId() const;
53 :
54 2490185 : bool operator==(const ExprIdToken& rhs) const {
55 2490185 : return getExpressionId() == rhs.getExpressionId();
56 : }
57 :
58 : bool operator<(const ExprIdToken& rhs) const {
59 : return getExpressionId() < rhs.getExpressionId();
60 : }
61 :
62 : template<class T, class U>
63 5187909 : friend bool operator!=(const T& lhs, const U& rhs)
64 : {
65 5187909 : return !(lhs == rhs);
66 : }
67 :
68 : template<class T, class U>
69 : friend bool operator<=(const T& lhs, const U& rhs)
70 : {
71 : return !(lhs > rhs);
72 : }
73 :
74 : template<class T, class U>
75 : friend bool operator>(const T& lhs, const U& rhs)
76 : {
77 : return rhs < lhs;
78 : }
79 :
80 : template<class T, class U>
81 : friend bool operator>=(const T& lhs, const U& rhs)
82 : {
83 : return !(lhs < rhs);
84 : }
85 :
86 : const Token& operator*() const NOEXCEPT {
87 : return *tok;
88 : }
89 :
90 : const Token* operator->() const NOEXCEPT {
91 : return tok;
92 : }
93 :
94 : struct Hash {
95 : std::size_t operator()(ExprIdToken etok) const;
96 : };
97 : };
98 :
99 : struct ProgramMemory {
100 : using Map = std::unordered_map<ExprIdToken, ValueFlow::Value, ExprIdToken::Hash>;
101 :
102 159523 : ProgramMemory() = default;
103 :
104 5957 : explicit ProgramMemory(Map values) : mValues(std::move(values)) {}
105 :
106 : void setValue(const Token* expr, const ValueFlow::Value& value);
107 : const ValueFlow::Value* getValue(nonneg int exprid, bool impossible = false) const;
108 :
109 : bool getIntValue(nonneg int exprid, MathLib::bigint& result) const;
110 : void setIntValue(const Token* expr, MathLib::bigint value, bool impossible = false);
111 :
112 : bool getContainerSizeValue(nonneg int exprid, MathLib::bigint& result) const;
113 : bool getContainerEmptyValue(nonneg int exprid, MathLib::bigint& result) const;
114 : void setContainerSizeValue(const Token* expr, MathLib::bigint value, bool isEqual = true);
115 :
116 : void setUnknown(const Token* expr);
117 :
118 : bool getTokValue(nonneg int exprid, const Token*& result) const;
119 : bool hasValue(nonneg int exprid);
120 :
121 : const ValueFlow::Value& at(nonneg int exprid) const;
122 : ValueFlow::Value& at(nonneg int exprid);
123 :
124 : void erase_if(const std::function<bool(const ExprIdToken&)>& pred);
125 :
126 : void swap(ProgramMemory &pm);
127 :
128 : void clear();
129 :
130 : bool empty() const;
131 :
132 : void replace(ProgramMemory pm);
133 :
134 : void insert(const ProgramMemory &pm);
135 :
136 212848 : Map::iterator begin() {
137 212848 : return mValues.begin();
138 : }
139 :
140 212849 : Map::iterator end() {
141 212849 : return mValues.end();
142 : }
143 :
144 0 : Map::const_iterator begin() const {
145 0 : return mValues.begin();
146 : }
147 :
148 0 : Map::const_iterator end() const {
149 0 : return mValues.end();
150 : }
151 :
152 0 : friend bool operator==(const ProgramMemory& x, const ProgramMemory& y) {
153 0 : return x.mValues == y.mValues;
154 : }
155 :
156 : friend bool operator!=(const ProgramMemory& x, const ProgramMemory& y) {
157 : return x.mValues != y.mValues;
158 : }
159 :
160 : private:
161 : Map mValues;
162 : };
163 :
164 : struct ProgramMemoryState {
165 : ProgramMemory state;
166 : std::map<nonneg int, const Token*> origins;
167 : const Settings* settings;
168 :
169 : explicit ProgramMemoryState(const Settings* s);
170 :
171 : void insert(const ProgramMemory &pm, const Token* origin = nullptr);
172 : void replace(ProgramMemory pm, const Token* origin = nullptr);
173 :
174 : void addState(const Token* tok, const ProgramMemory::Map& vars);
175 :
176 : void assume(const Token* tok, bool b, bool isEmpty = false);
177 :
178 : void removeModifiedVars(const Token* tok);
179 :
180 : ProgramMemory get(const Token* tok, const Token* ctx, const ProgramMemory::Map& vars) const;
181 : };
182 :
183 : std::vector<ValueFlow::Value> execute(const Scope* scope, ProgramMemory& pm, const Settings& settings);
184 :
185 : void execute(const Token* expr,
186 : ProgramMemory& programMemory,
187 : MathLib::bigint* result,
188 : bool* error,
189 : const Settings& settings);
190 :
191 : /**
192 : * Is condition always false when variable has given value?
193 : * \param condition top ast token in condition
194 : * \param pm program memory
195 : */
196 : bool conditionIsFalse(const Token* condition, ProgramMemory pm, const Settings& settings);
197 :
198 : /**
199 : * Is condition always true when variable has given value?
200 : * \param condition top ast token in condition
201 : * \param pm program memory
202 : */
203 : bool conditionIsTrue(const Token* condition, ProgramMemory pm, const Settings& settings);
204 :
205 : /**
206 : * Get program memory by looking backwards from given token.
207 : */
208 : ProgramMemory getProgramMemory(const Token* tok, const Token* expr, const ValueFlow::Value& value, const Settings& settings);
209 :
210 : ValueFlow::Value evaluateLibraryFunction(const std::unordered_map<nonneg int, ValueFlow::Value>& args,
211 : const std::string& returnValue,
212 : const Settings& settings,
213 : bool cpp);
214 :
215 : #endif
216 :
217 :
218 :
|
