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