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 namespace clang { 38 namespace ento { 39 40 DynamicTypeInfo getDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR) { 41 MR = MR->StripCasts(); 42 43 // Look up the dynamic type in the GDM. 44 if (const DynamicTypeInfo *DTI = State->get<DynamicTypeMap>(MR)) 45 return *DTI; 46 47 // Otherwise, fall back to what we know about the region. 48 if (const auto *TR = dyn_cast<TypedRegion>(MR)) 49 return DynamicTypeInfo(TR->getLocationType(), /*CanBeSub=*/false); 50 51 if (const auto *SR = dyn_cast<SymbolicRegion>(MR)) { 52 SymbolRef Sym = SR->getSymbol(); 53 return DynamicTypeInfo(Sym->getType()); 54 } 55 56 return {}; 57 } 58 59 const DynamicTypeInfo *getRawDynamicTypeInfo(ProgramStateRef State, 60 const MemRegion *MR) { 61 return State->get<DynamicTypeMap>(MR); 62 } 63 64 const DynamicCastInfo *getDynamicCastInfo(ProgramStateRef State, 65 const MemRegion *MR, 66 QualType CastFromTy, 67 QualType CastToTy) { 68 const auto *Lookup = State->get<DynamicCastMap>().lookup(MR); 69 if (!Lookup) 70 return nullptr; 71 72 for (const DynamicCastInfo &Cast : *Lookup) 73 if (Cast.equals(CastFromTy, CastToTy)) 74 return &Cast; 75 76 return nullptr; 77 } 78 79 ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR, 80 DynamicTypeInfo NewTy) { 81 State = State->set<DynamicTypeMap>(MR->StripCasts(), NewTy); 82 assert(State); 83 return State; 84 } 85 86 ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR, 87 QualType NewTy, bool CanBeSubClassed) { 88 return setDynamicTypeInfo(State, MR, DynamicTypeInfo(NewTy, CanBeSubClassed)); 89 } 90 91 ProgramStateRef setDynamicTypeAndCastInfo(ProgramStateRef State, 92 const MemRegion *MR, 93 QualType CastFromTy, 94 QualType CastToTy, 95 bool CastSucceeds) { 96 if (!MR) 97 return State; 98 99 if (CastSucceeds) { 100 assert((CastToTy->isAnyPointerType() || CastToTy->isReferenceType()) && 101 "DynamicTypeInfo should always be a pointer."); 102 State = State->set<DynamicTypeMap>(MR, CastToTy); 103 } 104 105 DynamicCastInfo::CastResult ResultKind = 106 CastSucceeds ? DynamicCastInfo::CastResult::Success 107 : DynamicCastInfo::CastResult::Failure; 108 109 CastSet::Factory &F = State->get_context<CastSet>(); 110 111 const CastSet *TempSet = State->get<DynamicCastMap>(MR); 112 CastSet Set = TempSet ? *TempSet : F.getEmptySet(); 113 114 Set = F.add(Set, {CastFromTy, CastToTy, ResultKind}); 115 State = State->set<DynamicCastMap>(MR, Set); 116 117 assert(State); 118 return State; 119 } 120 121 template <typename MapTy> 122 ProgramStateRef removeDead(ProgramStateRef State, const MapTy &Map, 123 SymbolReaper &SR) { 124 for (const auto &Elem : Map) 125 if (!SR.isLiveRegion(Elem.first)) 126 State = State->remove<DynamicCastMap>(Elem.first); 127 128 return State; 129 } 130 131 ProgramStateRef removeDeadTypes(ProgramStateRef State, SymbolReaper &SR) { 132 return removeDead(State, State->get<DynamicTypeMap>(), SR); 133 } 134 135 ProgramStateRef removeDeadCasts(ProgramStateRef State, SymbolReaper &SR) { 136 return removeDead(State, State->get<DynamicCastMap>(), SR); 137 } 138 139 static void printDynamicTypesJson(raw_ostream &Out, ProgramStateRef State, 140 const char *NL, unsigned int Space, 141 bool IsDot) { 142 Indent(Out, Space, IsDot) << "\"dynamic_types\": "; 143 144 const DynamicTypeMapTy &Map = State->get<DynamicTypeMap>(); 145 if (Map.isEmpty()) { 146 Out << "null," << NL; 147 return; 148 } 149 150 ++Space; 151 Out << '[' << NL; 152 for (DynamicTypeMapTy::iterator I = Map.begin(); I != Map.end(); ++I) { 153 const MemRegion *MR = I->first; 154 const DynamicTypeInfo &DTI = I->second; 155 Indent(Out, Space, IsDot) 156 << "{ \"region\": \"" << MR << "\", \"dyn_type\": "; 157 if (!DTI.isValid()) { 158 Out << "null"; 159 } else { 160 Out << '\"' << DTI.getType()->getPointeeType().getAsString() 161 << "\", \"sub_classable\": " 162 << (DTI.canBeASubClass() ? "true" : "false"); 163 } 164 Out << " }"; 165 166 if (std::next(I) != Map.end()) 167 Out << ','; 168 Out << NL; 169 } 170 171 --Space; 172 Indent(Out, Space, IsDot) << "]," << NL; 173 } 174 175 static void printDynamicCastsJson(raw_ostream &Out, ProgramStateRef State, 176 const char *NL, unsigned int Space, 177 bool IsDot) { 178 Indent(Out, Space, IsDot) << "\"dynamic_casts\": "; 179 180 const DynamicCastMapTy &Map = State->get<DynamicCastMap>(); 181 if (Map.isEmpty()) { 182 Out << "null," << NL; 183 return; 184 } 185 186 ++Space; 187 Out << '[' << NL; 188 for (DynamicCastMapTy::iterator I = Map.begin(); I != Map.end(); ++I) { 189 const MemRegion *MR = I->first; 190 const CastSet &Set = I->second; 191 192 Indent(Out, Space, IsDot) << "{ \"region\": \"" << MR << "\", \"casts\": "; 193 if (Set.isEmpty()) { 194 Out << "null "; 195 } else { 196 ++Space; 197 Out << '[' << NL; 198 for (CastSet::iterator SI = Set.begin(); SI != Set.end(); ++SI) { 199 Indent(Out, Space, IsDot) 200 << "{ \"from\": \"" << SI->from().getAsString() << "\", \"to\": \"" 201 << SI->to().getAsString() << "\", \"kind\": \"" 202 << (SI->succeeds() ? "success" : "fail") << "\" }"; 203 204 if (std::next(SI) != Set.end()) 205 Out << ','; 206 Out << NL; 207 } 208 --Space; 209 Indent(Out, Space, IsDot) << ']'; 210 } 211 Out << '}'; 212 213 if (std::next(I) != Map.end()) 214 Out << ','; 215 Out << NL; 216 } 217 218 --Space; 219 Indent(Out, Space, IsDot) << "]," << NL; 220 } 221 222 void printDynamicTypeInfoJson(raw_ostream &Out, ProgramStateRef State, 223 const char *NL, unsigned int Space, bool IsDot) { 224 printDynamicTypesJson(Out, State, NL, Space, IsDot); 225 printDynamicCastsJson(Out, State, NL, Space, IsDot); 226 } 227 228 } // namespace ento 229 } // namespace clang 230