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>(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
63const DynamicTypeInfo *getRawDynamicTypeInfo(ProgramStateRef State,
64                                             const MemRegion *MR) {
65  return State->get<DynamicTypeMap>(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(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
93DynamicTypeInfo getClassObjectDynamicTypeInfo(ProgramStateRef State,
94                                              SymbolRef Sym) {
95  const DynamicTypeInfo *DTI = State->get<DynamicClassObjectMap>(Sym);
96  return DTI ? *DTI : DynamicTypeInfo{};
97}
98
99ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR,
100                                   DynamicTypeInfo NewTy) {
101  State = State->set<DynamicTypeMap>(MR->StripCasts(), 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, 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>(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
144ProgramStateRef setClassObjectDynamicTypeInfo(ProgramStateRef State,
145                                              SymbolRef Sym,
146                                              DynamicTypeInfo NewTy) {
147  State = State->set<DynamicClassObjectMap>(Sym, NewTy);
148  return State;
149}
150
151ProgramStateRef setClassObjectDynamicTypeInfo(ProgramStateRef State,
152                                              SymbolRef Sym, QualType NewTy,
153                                              bool CanBeSubClassed) {
154  return setClassObjectDynamicTypeInfo(State, Sym,
155                                       DynamicTypeInfo(NewTy, CanBeSubClassed));
156}
157
158static bool isLive(SymbolReaper &SR, const MemRegion *MR) {
159  return SR.isLiveRegion(MR);
160}
161
162static bool isLive(SymbolReaper &SR, SymbolRef Sym) { return SR.isLive(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(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, "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, "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, "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