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. 27 REGISTER_MAP_WITH_PROGRAMSTATE(DynamicTypeMap, const clang::ento::MemRegion *, 28 clang::ento::DynamicTypeInfo) 29 30 /// A set factory of dynamic cast informations. 31 REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(CastSet, clang::ento::DynamicCastInfo) 32 33 /// A map from symbols to cast informations. 34 REGISTER_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. 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 93 DynamicTypeInfo getClassObjectDynamicTypeInfo(ProgramStateRef State, 94 SymbolRef Sym) { 95 const DynamicTypeInfo *DTI = State->get<DynamicClassObjectMap>(Sym); 96 return DTI ? *DTI : DynamicTypeInfo{}; 97 } 98 99 ProgramStateRef 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 106 ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR, 107 QualType NewTy, bool CanBeSubClassed) { 108 return setDynamicTypeInfo(State, MR, DynamicTypeInfo(NewTy, CanBeSubClassed)); 109 } 110 111 ProgramStateRef 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 144 ProgramStateRef setClassObjectDynamicTypeInfo(ProgramStateRef State, 145 SymbolRef Sym, 146 DynamicTypeInfo NewTy) { 147 State = State->set<DynamicClassObjectMap>(Sym, NewTy); 148 return State; 149 } 150 151 ProgramStateRef setClassObjectDynamicTypeInfo(ProgramStateRef State, 152 SymbolRef Sym, QualType NewTy, 153 bool CanBeSubClassed) { 154 return setClassObjectDynamicTypeInfo(State, Sym, 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 175 ProgramStateRef removeDeadTypes(ProgramStateRef State, SymbolReaper &SR) { 176 return removeDeadImpl<DynamicTypeMap>(State, SR); 177 } 178 179 ProgramStateRef removeDeadCasts(ProgramStateRef State, SymbolReaper &SR) { 180 return removeDeadImpl<DynamicCastMap>(State, SR); 181 } 182 183 ProgramStateRef 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 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 << "\", \"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() << "\", \"to\": \"" << DCI.to() 221 << "\", \"kind\": \"" << (DCI.succeeds() ? "success" : "fail") 222 << "\""; 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, 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 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 307