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.
27REGISTER_MAP_WITH_PROGRAMSTATE(DynamicTypeMap, const clang::ento::MemRegion *,
28 clang::ento::DynamicTypeInfo)
29
30/// A set factory of dynamic cast informations.
31REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(CastSet, clang::ento::DynamicCastInfo)
32
33/// A map from symbols to cast informations.
34REGISTER_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.
38REGISTER_MAP_WITH_PROGRAMSTATE(DynamicClassObjectMap, clang::ento::SymbolRef,
39 clang::ento::DynamicTypeInfo)
40
41namespace clang {
42namespace ento {
43
44DynamicTypeInfo 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
63const DynamicTypeInfo *getRawDynamicTypeInfo(ProgramStateRef State,
64 const MemRegion *MR) {
65 return State->get<DynamicTypeMap>(key: MR);
66}
67
68static 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
75const 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
93DynamicTypeInfo getClassObjectDynamicTypeInfo(ProgramStateRef State,
94 SymbolRef Sym) {
95 const DynamicTypeInfo *DTI = State->get<DynamicClassObjectMap>(key: Sym);
96 return DTI ? *DTI : DynamicTypeInfo{};
97}
98
99ProgramStateRef 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
106ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR,
107 QualType NewTy, bool CanBeSubClassed) {
108 return setDynamicTypeInfo(State, MR, NewTy: DynamicTypeInfo(NewTy, CanBeSubClassed));
109}
110
111ProgramStateRef 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
144ProgramStateRef setClassObjectDynamicTypeInfo(ProgramStateRef State,
145 SymbolRef Sym,
146 DynamicTypeInfo NewTy) {
147 State = State->set<DynamicClassObjectMap>(K: Sym, E: NewTy);
148 return State;
149}
150
151ProgramStateRef setClassObjectDynamicTypeInfo(ProgramStateRef State,
152 SymbolRef Sym, QualType NewTy,
153 bool CanBeSubClassed) {
154 return setClassObjectDynamicTypeInfo(State, Sym,
155 NewTy: DynamicTypeInfo(NewTy, CanBeSubClassed));
156}
157
158static bool isLive(SymbolReaper &SR, const MemRegion *MR) {
159 return SR.isLiveRegion(region: MR);
160}
161
162static bool isLive(SymbolReaper &SR, SymbolRef Sym) { return SR.isLive(sym: Sym); }
163
164template <typename MapTy>
165static 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
175ProgramStateRef removeDeadTypes(ProgramStateRef State, SymbolReaper &SR) {
176 return removeDeadImpl<DynamicTypeMap>(State, SR);
177}
178
179ProgramStateRef removeDeadCasts(ProgramStateRef State, SymbolReaper &SR) {
180 return removeDeadImpl<DynamicCastMap>(State, SR);
181}
182
183ProgramStateRef 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
192static 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
197static 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
202static 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
218static 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
225template <class T, class U>
226static 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
232template <class ContainerTy>
233static 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
257static 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
263template <class MapTy>
264static 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
275static 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
281static 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
287static 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
298void 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

source code of clang/lib/StaticAnalyzer/Core/DynamicType.cpp