clang  11.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.
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 const DynamicCastInfo *getDynamicCastInfo(ProgramStateRef State,
69  const MemRegion *MR,
70  QualType CastFromTy,
71  QualType CastToTy) {
72  const auto *Lookup = State->get<DynamicCastMap>().lookup(MR);
73  if (!Lookup)
74  return nullptr;
75 
76  for (const DynamicCastInfo &Cast : *Lookup)
77  if (Cast.equals(CastFromTy, CastToTy))
78  return &Cast;
79 
80  return nullptr;
81 }
82 
84  SymbolRef Sym) {
85  const DynamicTypeInfo *DTI = State->get<DynamicClassObjectMap>(Sym);
86  return DTI ? *DTI : DynamicTypeInfo{};
87 }
88 
89 ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR,
90  DynamicTypeInfo NewTy) {
91  State = State->set<DynamicTypeMap>(MR->StripCasts(), NewTy);
92  assert(State);
93  return State;
94 }
95 
96 ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR,
97  QualType NewTy, bool CanBeSubClassed) {
98  return setDynamicTypeInfo(State, MR, DynamicTypeInfo(NewTy, CanBeSubClassed));
99 }
100 
102  const MemRegion *MR,
103  QualType CastFromTy,
104  QualType CastToTy,
105  bool CastSucceeds) {
106  if (!MR)
107  return State;
108 
109  if (CastSucceeds) {
110  assert((CastToTy->isAnyPointerType() || CastToTy->isReferenceType()) &&
111  "DynamicTypeInfo should always be a pointer.");
112  State = State->set<DynamicTypeMap>(MR, CastToTy);
113  }
114 
115  DynamicCastInfo::CastResult ResultKind =
116  CastSucceeds ? DynamicCastInfo::CastResult::Success
117  : DynamicCastInfo::CastResult::Failure;
118 
119  CastSet::Factory &F = State->get_context<CastSet>();
120 
121  const CastSet *TempSet = State->get<DynamicCastMap>(MR);
122  CastSet Set = TempSet ? *TempSet : F.getEmptySet();
123 
124  Set = F.add(Set, {CastFromTy, CastToTy, ResultKind});
125  State = State->set<DynamicCastMap>(MR, Set);
126 
127  assert(State);
128  return State;
129 }
130 
132  SymbolRef Sym,
133  DynamicTypeInfo NewTy) {
134  State = State->set<DynamicClassObjectMap>(Sym, NewTy);
135  return State;
136 }
137 
139  SymbolRef Sym, QualType NewTy,
140  bool CanBeSubClassed) {
141  return setClassObjectDynamicTypeInfo(State, Sym,
142  DynamicTypeInfo(NewTy, CanBeSubClassed));
143 }
144 
145 static bool isLive(SymbolReaper &SR, const MemRegion *MR) {
146  return SR.isLiveRegion(MR);
147 }
148 
149 static bool isLive(SymbolReaper &SR, SymbolRef Sym) { return SR.isLive(Sym); }
150 
151 template <typename MapTy>
152 static ProgramStateRef removeDeadImpl(ProgramStateRef State, SymbolReaper &SR) {
153  const auto &Map = State->get<MapTy>();
154 
155  for (const auto &Elem : Map)
156  if (!isLive(SR, Elem.first))
157  State = State->remove<MapTy>(Elem.first);
158 
159  return State;
160 }
161 
162 ProgramStateRef removeDeadTypes(ProgramStateRef State, SymbolReaper &SR) {
163  return removeDeadImpl<DynamicTypeMap>(State, SR);
164 }
165 
166 ProgramStateRef removeDeadCasts(ProgramStateRef State, SymbolReaper &SR) {
167  return removeDeadImpl<DynamicCastMap>(State, SR);
168 }
169 
171  SymbolReaper &SR) {
172  return removeDeadImpl<DynamicClassObjectMap>(State, SR);
173 }
174 
175 //===----------------------------------------------------------------------===//
176 // Implementation of the 'printer-to-JSON' function
177 //===----------------------------------------------------------------------===//
178 
179 static raw_ostream &printJson(const MemRegion *Region, raw_ostream &Out,
180  const char *NL, unsigned int Space, bool IsDot) {
181  return Out << "\"region\": \"" << Region << "\"";
182 }
183 
184 static raw_ostream &printJson(const SymExpr *Symbol, raw_ostream &Out,
185  const char *NL, unsigned int Space, bool IsDot) {
186  return Out << "\"symbol\": \"" << Symbol << "\"";
187 }
188 
189 static raw_ostream &printJson(const DynamicTypeInfo &DTI, raw_ostream &Out,
190  const char *NL, unsigned int Space, bool IsDot) {
191  Out << "\"dyn_type\": ";
192  if (!DTI.isValid()) {
193  Out << "null";
194  } else {
195  QualType ToPrint = DTI.getType();
196  if (ToPrint->isAnyPointerType())
197  ToPrint = ToPrint->getPointeeType();
198 
199  Out << '\"' << ToPrint.getAsString() << "\", \"sub_classable\": "
200  << (DTI.canBeASubClass() ? "true" : "false");
201  }
202  return Out;
203 }
204 
205 static raw_ostream &printJson(const DynamicCastInfo &DCI, raw_ostream &Out,
206  const char *NL, unsigned int Space, bool IsDot) {
207  return Out << "\"from\": \"" << DCI.from().getAsString() << "\", \"to\": \""
208  << DCI.to().getAsString() << "\", \"kind\": \""
209  << (DCI.succeeds() ? "success" : "fail") << "\"";
210 }
211 
212 template <class T, class U>
213 static raw_ostream &printJson(const std::pair<T, U> &Pair, raw_ostream &Out,
214  const char *NL, unsigned int Space, bool IsDot) {
215  printJson(Pair.first, Out, NL, Space, IsDot) << ", ";
216  return printJson(Pair.second, Out, NL, Space, IsDot);
217 }
218 
219 template <class ContainerTy>
220 static raw_ostream &printJsonContainer(const ContainerTy &Container,
221  raw_ostream &Out, const char *NL,
222  unsigned int Space, bool IsDot) {
223  if (Container.isEmpty()) {
224  return Out << "null";
225  }
226 
227  ++Space;
228  Out << '[' << NL;
229  for (auto I = Container.begin(); I != Container.end(); ++I) {
230  const auto &Element = *I;
231 
232  Indent(Out, Space, IsDot) << "{ ";
233  printJson(Element, Out, NL, Space, IsDot) << " }";
234 
235  if (std::next(I) != Container.end())
236  Out << ',';
237  Out << NL;
238  }
239 
240  --Space;
241  return Indent(Out, Space, IsDot) << "]";
242 }
243 
244 static raw_ostream &printJson(const CastSet &Set, raw_ostream &Out,
245  const char *NL, unsigned int Space, bool IsDot) {
246  Out << "\"casts\": ";
247  return printJsonContainer(Set, Out, NL, Space, IsDot);
248 }
249 
250 template <class MapTy>
251 static void printJsonImpl(raw_ostream &Out, ProgramStateRef State,
252  const char *Name, const char *NL, unsigned int Space,
253  bool IsDot, bool PrintEvenIfEmpty = true) {
254  const auto &Map = State->get<MapTy>();
255  if (Map.isEmpty() && !PrintEvenIfEmpty)
256  return;
257 
258  Indent(Out, Space, IsDot) << "\"" << Name << "\": ";
259  printJsonContainer(Map, Out, NL, Space, IsDot) << "," << NL;
260 }
261 
262 static void printDynamicTypesJson(raw_ostream &Out, ProgramStateRef State,
263  const char *NL, unsigned int Space,
264  bool IsDot) {
265  printJsonImpl<DynamicTypeMap>(Out, State, "dynamic_types", NL, Space, IsDot);
266 }
267 
268 static void printDynamicCastsJson(raw_ostream &Out, ProgramStateRef State,
269  const char *NL, unsigned int Space,
270  bool IsDot) {
271  printJsonImpl<DynamicCastMap>(Out, State, "dynamic_casts", NL, Space, IsDot);
272 }
273 
274 static void printClassObjectDynamicTypesJson(raw_ostream &Out,
275  ProgramStateRef State,
276  const char *NL, unsigned int Space,
277  bool IsDot) {
278  // Let's print Class object type information only if we have something
279  // meaningful to print.
280  printJsonImpl<DynamicClassObjectMap>(Out, State, "class_object_types", NL,
281  Space, IsDot,
282  /*PrintEvenIfEmpty=*/false);
283 }
284 
285 void printDynamicTypeInfoJson(raw_ostream &Out, ProgramStateRef State,
286  const char *NL, unsigned int Space, bool IsDot) {
287  printDynamicTypesJson(Out, State, NL, Space, IsDot);
288  printDynamicCastsJson(Out, State, NL, Space, IsDot);
289  printClassObjectDynamicTypesJson(Out, State, NL, Space, IsDot);
290 }
291 
292 } // namespace ento
293 } // namespace clang
bool Cast(InterpState &S, CodePtr OpPC)
Definition: Interp.h:800
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:94
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.
ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR, DynamicTypeInfo NewTy)
Set dynamic type information of the region; return the new state.
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
llvm::DenseMap< Stmt *, Stmt * > MapTy
Definition: ParentMap.cpp:22
const SymExpr * SymbolRef
Definition: SymExpr.h:110
LineState State
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
ProgramStateRef removeDeadCasts(ProgramStateRef State, SymbolReaper &SR)
Removes the dead cast informations from State.
const DynamicCastInfo * getDynamicCastInfo(ProgramStateRef State, const MemRegion *MR, QualType CastFromTy, QualType CastToTy)
Get dynamic cast information from CastFromTy to CastToTy of MR.
ProgramStateRef removeDeadTypes(ProgramStateRef State, SymbolReaper &SR)
Removes the dead type informations from State.
Stores the currently inferred strictest bound on the runtime type of a region in a given state along ...
ProgramStateRef setClassObjectDynamicTypeInfo(ProgramStateRef State, SymbolRef Sym, DynamicTypeInfo NewTy)
Set constraint on a type contained in a class object; return the new state.
#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...
Dataflow Directional Tag Classes.
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.
DynamicTypeInfo getClassObjectDynamicTypeInfo(ProgramStateRef State, SymbolRef Sym)
Get dynamic type information stored in a class object represented by Sym.
DynamicTypeInfo getDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR)
Get dynamic type information for the region MR.
void printDynamicTypeInfoJson(raw_ostream &Out, ProgramStateRef State, const char *NL="\, unsigned int Space=0, bool IsDot=false)
ProgramStateRef removeDeadClassObjectTypes(ProgramStateRef State, SymbolReaper &SR)
Removes the dead Class object type informations from State.
const DynamicTypeInfo * getRawDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR)
Get raw dynamic type information for the region MR.