clang  14.0.0git
DynamicType.cpp
Go to the documentation of this file.
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 
17 #include "clang/Basic/LLVM.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.
29 
30 /// A set factory of dynamic cast informations.
32 
33 /// A map from symbols to cast informations.
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>(MR))
49  return *DTI;
50 
51  // Otherwise, fall back to what we know about the region.
52  if (const auto *TR = dyn_cast<TypedRegion>(MR))
53  return DynamicTypeInfo(TR->getLocationType(), /*CanBeSub=*/false);
54 
55  if (const auto *SR = dyn_cast<SymbolicRegion>(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>(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(MR);
80  if (!Lookup)
81  return nullptr;
82 
83  unbox(CastFromTy);
84  unbox(CastToTy);
85 
86  for (const DynamicCastInfo &Cast : *Lookup)
87  if (Cast.equals(CastFromTy, CastToTy))
88  return &Cast;
89 
90  return nullptr;
91 }
92 
94  SymbolRef Sym) {
95  const DynamicTypeInfo *DTI = State->get<DynamicClassObjectMap>(Sym);
96  return DTI ? *DTI : DynamicTypeInfo{};
97 }
98 
100  DynamicTypeInfo NewTy) {
101  State = State->set<DynamicTypeMap>(MR->StripCasts(), NewTy);
102  assert(State);
103  return State;
104 }
105 
107  QualType NewTy, bool CanBeSubClassed) {
108  return setDynamicTypeInfo(State, MR, DynamicTypeInfo(NewTy, CanBeSubClassed));
109 }
110 
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>(MR, CastToTy);
123  }
124 
125  unbox(CastFromTy);
126  unbox(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>(MR);
135  CastSet Set = TempSet ? *TempSet : F.getEmptySet();
136 
137  Set = F.add(Set, {CastFromTy, CastToTy, ResultKind});
138  State = State->set<DynamicCastMap>(MR, Set);
139 
140  assert(State);
141  return State;
142 }
143 
145  SymbolRef Sym,
146  DynamicTypeInfo NewTy) {
147  State = State->set<DynamicClassObjectMap>(Sym, NewTy);
148  return State;
149 }
150 
152  SymbolRef Sym, QualType NewTy,
153  bool CanBeSubClassed) {
155  DynamicTypeInfo(NewTy, CanBeSubClassed));
156 }
157 
158 static bool isLive(SymbolReaper &SR, const MemRegion *MR) {
159  return SR.isLiveRegion(MR);
160 }
161 
162 static bool isLive(SymbolReaper &SR, SymbolRef Sym) { return SR.isLive(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 
176  return removeDeadImpl<DynamicTypeMap>(State, SR);
177 }
178 
180  return removeDeadImpl<DynamicCastMap>(State, SR);
181 }
182 
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.getAsString() << "\", \"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().getAsString() << "\", \"to\": \""
221  << DCI.to().getAsString() << "\", \"kind\": \""
222  << (DCI.succeeds() ? "success" : "fail") << "\"";
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(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, "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, "dynamic_casts", NL, Space, IsDot);
285 }
286 
287 static void printClassObjectDynamicTypesJson(raw_ostream &Out,
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, "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
clang::ento::setDynamicTypeInfo
ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR, DynamicTypeInfo NewTy)
Set dynamic type information of the region; return the new state.
REGISTER_SET_FACTORY_WITH_PROGRAMSTATE
#define REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(Name, Elem)
Declares an immutable set type Name and registers the factory for such sets in the program state,...
Definition: ProgramStateTrait.h:116
clang::ento::removeDeadClassObjectTypes
ProgramStateRef removeDeadClassObjectTypes(ProgramStateRef State, SymbolReaper &SR)
Removes the dead Class object type informations from State.
clang::ento::DynamicTypeInfo
Stores the currently inferred strictest bound on the runtime type of a region in a given state along ...
Definition: DynamicTypeInfo.h:19
clang::ento::ProgramStateRef
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
Definition: ProgramState_Fwd.h:37
REGISTER_MAP_WITH_PROGRAMSTATE
REGISTER_MAP_WITH_PROGRAMSTATE(DynamicTypeMap, const clang::ento::MemRegion *, clang::ento::DynamicTypeInfo) REGISTER_MAP_WITH_PROGRAMSTATE(DynamicCastMap
The GDM component containing the dynamic type info.
clang::ento::SymbolRef
const SymExpr * SymbolRef
Definition: SymExpr.h:110
clang::ento::printDynamicTypeInfoJson
void printDynamicTypeInfoJson(raw_ostream &Out, ProgramStateRef State, const char *NL="\n", unsigned int Space=0, bool IsDot=false)
clang::ento::MemRegion
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:94
clang::ento::removeDeadCasts
ProgramStateRef removeDeadCasts(ProgramStateRef State, SymbolReaper &SR)
Removes the dead cast informations from State.
JsonSupport.h
SymExpr.h
clang::ento::DynamicCastInfo
Definition: DynamicCastInfo.h:17
clang::ento::setClassObjectDynamicTypeInfo
ProgramStateRef setClassObjectDynamicTypeInfo(ProgramStateRef State, SymbolRef Sym, DynamicTypeInfo NewTy)
Set constraint on a type contained in a class object; return the new state.
clang::ento::getDynamicCastInfo
const DynamicCastInfo * getDynamicCastInfo(ProgramStateRef State, const MemRegion *MR, QualType CastFromTy, QualType CastToTy)
Get dynamic cast information from CastFromTy to CastToTy of MR.
clang::interp::Cast
bool Cast(InterpState &S, CodePtr OpPC)
Definition: Interp.h:802
MapTy
llvm::DenseMap< Stmt *, Stmt * > MapTy
Definition: ParentMap.cpp:22
clang::ento::removeDeadTypes
ProgramStateRef removeDeadTypes(ProgramStateRef State, SymbolReaper &SR)
Removes the dead type informations from State.
clang::ento::setDynamicTypeAndCastInfo
ProgramStateRef setDynamicTypeAndCastInfo(ProgramStateRef State, const MemRegion *MR, QualType CastFromTy, QualType CastToTy, bool IsCastSucceeds)
Set dynamic type and cast information of the region; return the new state.
LLVM.h
State
LineState State
Definition: UnwrappedLineFormatter.cpp:986
ProgramState.h
clang
Definition: CalledOnceCheck.h:17
MemRegion.h
clang::ento::getDynamicTypeInfo
DynamicTypeInfo getDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR)
Get dynamic type information for the region MR.
DynamicType.h
clang::ento::getClassObjectDynamicTypeInfo
DynamicTypeInfo getClassObjectDynamicTypeInfo(ProgramStateRef State, SymbolRef Sym)
Get dynamic type information stored in a class object represented by Sym.
clang::ento::getRawDynamicTypeInfo
const DynamicTypeInfo * getRawDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR)
Get raw dynamic type information for the region MR.