1 | //===- DynamicType.cpp - Dynamic type related APIs --------------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file defines APIs that track and query dynamic type information. This |
10 | // information can be used to devirtualize calls during the symbolic execution |
11 | // or do type checking. |
12 | // |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h" |
16 | #include "clang/Basic/JsonSupport.h" |
17 | #include "clang/Basic/LLVM.h" |
18 | #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" |
19 | #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" |
20 | #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" |
21 | #include "llvm/Support/Casting.h" |
22 | #include "llvm/Support/raw_ostream.h" |
23 | #include <cassert> |
24 | |
25 | /// The GDM component containing the dynamic type info. This is a map from a |
26 | /// symbol to its most likely type. |
27 | REGISTER_MAP_WITH_PROGRAMSTATE(DynamicTypeMap, const clang::ento::MemRegion *, |
28 | clang::ento::DynamicTypeInfo) |
29 | |
30 | /// A set factory of dynamic cast informations. |
31 | REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(CastSet, clang::ento::DynamicCastInfo) |
32 | |
33 | /// A map from symbols to cast informations. |
34 | REGISTER_MAP_WITH_PROGRAMSTATE(DynamicCastMap, const clang::ento::MemRegion *, |
35 | CastSet) |
36 | |
37 | // A map from Class object symbols to the most likely pointed-to type. |
38 | REGISTER_MAP_WITH_PROGRAMSTATE(DynamicClassObjectMap, clang::ento::SymbolRef, |
39 | clang::ento::DynamicTypeInfo) |
40 | |
41 | namespace clang { |
42 | namespace ento { |
43 | |
44 | DynamicTypeInfo getDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR) { |
45 | MR = MR->StripCasts(); |
46 | |
47 | // Look up the dynamic type in the GDM. |
48 | if (const DynamicTypeInfo *DTI = State->get<DynamicTypeMap>(key: MR)) |
49 | return *DTI; |
50 | |
51 | // Otherwise, fall back to what we know about the region. |
52 | if (const auto *TR = dyn_cast<TypedRegion>(Val: MR)) |
53 | return DynamicTypeInfo(TR->getLocationType(), /*CanBeSub=*/false); |
54 | |
55 | if (const auto *SR = dyn_cast<SymbolicRegion>(Val: MR)) { |
56 | SymbolRef Sym = SR->getSymbol(); |
57 | return DynamicTypeInfo(Sym->getType()); |
58 | } |
59 | |
60 | return {}; |
61 | } |
62 | |
63 | const DynamicTypeInfo *getRawDynamicTypeInfo(ProgramStateRef State, |
64 | const MemRegion *MR) { |
65 | return State->get<DynamicTypeMap>(key: MR); |
66 | } |
67 | |
68 | static void unbox(QualType &Ty) { |
69 | // FIXME: Why are we being fed references to pointers in the first place? |
70 | while (Ty->isReferenceType() || Ty->isPointerType()) |
71 | Ty = Ty->getPointeeType(); |
72 | Ty = Ty.getCanonicalType().getUnqualifiedType(); |
73 | } |
74 | |
75 | const DynamicCastInfo *getDynamicCastInfo(ProgramStateRef State, |
76 | const MemRegion *MR, |
77 | QualType CastFromTy, |
78 | QualType CastToTy) { |
79 | const auto *Lookup = State->get<DynamicCastMap>().lookup(K: MR); |
80 | if (!Lookup) |
81 | return nullptr; |
82 | |
83 | unbox(Ty&: CastFromTy); |
84 | unbox(Ty&: CastToTy); |
85 | |
86 | for (const DynamicCastInfo &Cast : *Lookup) |
87 | if (Cast.equals(CastFromTy, CastToTy)) |
88 | return &Cast; |
89 | |
90 | return nullptr; |
91 | } |
92 | |
93 | DynamicTypeInfo getClassObjectDynamicTypeInfo(ProgramStateRef State, |
94 | SymbolRef Sym) { |
95 | const DynamicTypeInfo *DTI = State->get<DynamicClassObjectMap>(key: Sym); |
96 | return DTI ? *DTI : DynamicTypeInfo{}; |
97 | } |
98 | |
99 | ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR, |
100 | DynamicTypeInfo NewTy) { |
101 | State = State->set<DynamicTypeMap>(K: MR->StripCasts(), E: NewTy); |
102 | assert(State); |
103 | return State; |
104 | } |
105 | |
106 | ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR, |
107 | QualType NewTy, bool CanBeSubClassed) { |
108 | return setDynamicTypeInfo(State, MR, NewTy: DynamicTypeInfo(NewTy, CanBeSubClassed)); |
109 | } |
110 | |
111 | ProgramStateRef setDynamicTypeAndCastInfo(ProgramStateRef State, |
112 | const MemRegion *MR, |
113 | QualType CastFromTy, |
114 | QualType CastToTy, |
115 | bool CastSucceeds) { |
116 | if (!MR) |
117 | return State; |
118 | |
119 | if (CastSucceeds) { |
120 | assert((CastToTy->isAnyPointerType() || CastToTy->isReferenceType()) && |
121 | "DynamicTypeInfo should always be a pointer." ); |
122 | State = State->set<DynamicTypeMap>(K: MR, E: CastToTy); |
123 | } |
124 | |
125 | unbox(Ty&: CastFromTy); |
126 | unbox(Ty&: CastToTy); |
127 | |
128 | DynamicCastInfo::CastResult ResultKind = |
129 | CastSucceeds ? DynamicCastInfo::CastResult::Success |
130 | : DynamicCastInfo::CastResult::Failure; |
131 | |
132 | CastSet::Factory &F = State->get_context<CastSet>(); |
133 | |
134 | const CastSet *TempSet = State->get<DynamicCastMap>(key: MR); |
135 | CastSet Set = TempSet ? *TempSet : F.getEmptySet(); |
136 | |
137 | Set = F.add(Old: Set, V: {CastFromTy, CastToTy, ResultKind}); |
138 | State = State->set<DynamicCastMap>(K: MR, E: Set); |
139 | |
140 | assert(State); |
141 | return State; |
142 | } |
143 | |
144 | ProgramStateRef setClassObjectDynamicTypeInfo(ProgramStateRef State, |
145 | SymbolRef Sym, |
146 | DynamicTypeInfo NewTy) { |
147 | State = State->set<DynamicClassObjectMap>(K: Sym, E: NewTy); |
148 | return State; |
149 | } |
150 | |
151 | ProgramStateRef setClassObjectDynamicTypeInfo(ProgramStateRef State, |
152 | SymbolRef Sym, QualType NewTy, |
153 | bool CanBeSubClassed) { |
154 | return setClassObjectDynamicTypeInfo(State, Sym, |
155 | NewTy: DynamicTypeInfo(NewTy, CanBeSubClassed)); |
156 | } |
157 | |
158 | static bool isLive(SymbolReaper &SR, const MemRegion *MR) { |
159 | return SR.isLiveRegion(region: MR); |
160 | } |
161 | |
162 | static bool isLive(SymbolReaper &SR, SymbolRef Sym) { return SR.isLive(sym: Sym); } |
163 | |
164 | template <typename MapTy> |
165 | static ProgramStateRef removeDeadImpl(ProgramStateRef State, SymbolReaper &SR) { |
166 | const auto &Map = State->get<MapTy>(); |
167 | |
168 | for (const auto &Elem : Map) |
169 | if (!isLive(SR, Elem.first)) |
170 | State = State->remove<MapTy>(Elem.first); |
171 | |
172 | return State; |
173 | } |
174 | |
175 | ProgramStateRef removeDeadTypes(ProgramStateRef State, SymbolReaper &SR) { |
176 | return removeDeadImpl<DynamicTypeMap>(State, SR); |
177 | } |
178 | |
179 | ProgramStateRef removeDeadCasts(ProgramStateRef State, SymbolReaper &SR) { |
180 | return removeDeadImpl<DynamicCastMap>(State, SR); |
181 | } |
182 | |
183 | ProgramStateRef removeDeadClassObjectTypes(ProgramStateRef State, |
184 | SymbolReaper &SR) { |
185 | return removeDeadImpl<DynamicClassObjectMap>(State, SR); |
186 | } |
187 | |
188 | //===----------------------------------------------------------------------===// |
189 | // Implementation of the 'printer-to-JSON' function |
190 | //===----------------------------------------------------------------------===// |
191 | |
192 | static raw_ostream &printJson(const MemRegion *Region, raw_ostream &Out, |
193 | const char *NL, unsigned int Space, bool IsDot) { |
194 | return Out << "\"region\": \"" << Region << "\"" ; |
195 | } |
196 | |
197 | static raw_ostream &printJson(const SymExpr *Symbol, raw_ostream &Out, |
198 | const char *NL, unsigned int Space, bool IsDot) { |
199 | return Out << "\"symbol\": \"" << Symbol << "\"" ; |
200 | } |
201 | |
202 | static raw_ostream &printJson(const DynamicTypeInfo &DTI, raw_ostream &Out, |
203 | const char *NL, unsigned int Space, bool IsDot) { |
204 | Out << "\"dyn_type\": " ; |
205 | if (!DTI.isValid()) { |
206 | Out << "null" ; |
207 | } else { |
208 | QualType ToPrint = DTI.getType(); |
209 | if (ToPrint->isAnyPointerType()) |
210 | ToPrint = ToPrint->getPointeeType(); |
211 | |
212 | Out << '\"' << ToPrint << "\", \"sub_classable\": " |
213 | << (DTI.canBeASubClass() ? "true" : "false" ); |
214 | } |
215 | return Out; |
216 | } |
217 | |
218 | static raw_ostream &printJson(const DynamicCastInfo &DCI, raw_ostream &Out, |
219 | const char *NL, unsigned int Space, bool IsDot) { |
220 | return Out << "\"from\": \"" << DCI.from() << "\", \"to\": \"" << DCI.to() |
221 | << "\", \"kind\": \"" << (DCI.succeeds() ? "success" : "fail" ) |
222 | << "\"" ; |
223 | } |
224 | |
225 | template <class T, class U> |
226 | static raw_ostream &printJson(const std::pair<T, U> &Pair, raw_ostream &Out, |
227 | const char *NL, unsigned int Space, bool IsDot) { |
228 | printJson(Pair.first, Out, NL, Space, IsDot) << ", " ; |
229 | return printJson(Pair.second, Out, NL, Space, IsDot); |
230 | } |
231 | |
232 | template <class ContainerTy> |
233 | static raw_ostream &printJsonContainer(const ContainerTy &Container, |
234 | raw_ostream &Out, const char *NL, |
235 | unsigned int Space, bool IsDot) { |
236 | if (Container.isEmpty()) { |
237 | return Out << "null" ; |
238 | } |
239 | |
240 | ++Space; |
241 | Out << '[' << NL; |
242 | for (auto I = Container.begin(); I != Container.end(); ++I) { |
243 | const auto &Element = *I; |
244 | |
245 | Indent(Out, Space, IsDot) << "{ " ; |
246 | printJson(Element, Out, NL, Space, IsDot) << " }" ; |
247 | |
248 | if (std::next(I) != Container.end()) |
249 | Out << ','; |
250 | Out << NL; |
251 | } |
252 | |
253 | --Space; |
254 | return Indent(Out, Space, IsDot) << "]" ; |
255 | } |
256 | |
257 | static raw_ostream &printJson(const CastSet &Set, raw_ostream &Out, |
258 | const char *NL, unsigned int Space, bool IsDot) { |
259 | Out << "\"casts\": " ; |
260 | return printJsonContainer(Container: Set, Out, NL, Space, IsDot); |
261 | } |
262 | |
263 | template <class MapTy> |
264 | static void printJsonImpl(raw_ostream &Out, ProgramStateRef State, |
265 | const char *Name, const char *NL, unsigned int Space, |
266 | bool IsDot, bool PrintEvenIfEmpty = true) { |
267 | const auto &Map = State->get<MapTy>(); |
268 | if (Map.isEmpty() && !PrintEvenIfEmpty) |
269 | return; |
270 | |
271 | Indent(Out, Space, IsDot) << "\"" << Name << "\": " ; |
272 | printJsonContainer(Map, Out, NL, Space, IsDot) << "," << NL; |
273 | } |
274 | |
275 | static void printDynamicTypesJson(raw_ostream &Out, ProgramStateRef State, |
276 | const char *NL, unsigned int Space, |
277 | bool IsDot) { |
278 | printJsonImpl<DynamicTypeMap>(Out, State, Name: "dynamic_types" , NL, Space, IsDot); |
279 | } |
280 | |
281 | static void printDynamicCastsJson(raw_ostream &Out, ProgramStateRef State, |
282 | const char *NL, unsigned int Space, |
283 | bool IsDot) { |
284 | printJsonImpl<DynamicCastMap>(Out, State, Name: "dynamic_casts" , NL, Space, IsDot); |
285 | } |
286 | |
287 | static void printClassObjectDynamicTypesJson(raw_ostream &Out, |
288 | ProgramStateRef State, |
289 | const char *NL, unsigned int Space, |
290 | bool IsDot) { |
291 | // Let's print Class object type information only if we have something |
292 | // meaningful to print. |
293 | printJsonImpl<DynamicClassObjectMap>(Out, State, Name: "class_object_types" , NL, |
294 | Space, IsDot, |
295 | /*PrintEvenIfEmpty=*/false); |
296 | } |
297 | |
298 | void printDynamicTypeInfoJson(raw_ostream &Out, ProgramStateRef State, |
299 | const char *NL, unsigned int Space, bool IsDot) { |
300 | printDynamicTypesJson(Out, State, NL, Space, IsDot); |
301 | printDynamicCastsJson(Out, State, NL, Space, IsDot); |
302 | printClassObjectDynamicTypesJson(Out, State, NL, Space, IsDot); |
303 | } |
304 | |
305 | } // namespace ento |
306 | } // namespace clang |
307 | |