mikt | e6f6ec4 | 2023-06-21 23:01:15 | [diff] [blame] | 1 | // Copyright 2023 The Chromium Authors |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
| 5 | #ifndef TOOLS_CLANG_PLUGINS_TYPEPREDICATEUTIL_H_ |
| 6 | #define TOOLS_CLANG_PLUGINS_TYPEPREDICATEUTIL_H_ |
| 7 | |
| 8 | #include<map> |
| 9 | #include<memory> |
| 10 | #include<optional> |
| 11 | #include<set> |
| 12 | #include<string> |
| 13 | #include<vector> |
| 14 | |
| 15 | #include"clang/AST/Decl.h" |
| 16 | #include"clang/AST/DeclTemplate.h" |
| 17 | #include"clang/AST/Type.h" |
| 18 | #include"llvm/ADT/ScopeExit.h" |
| 19 | |
| 20 | enumclassInductionRule:unsigned{ |
| 21 | kNone=0, |
| 22 | kPointerPointee=(1<<0), |
| 23 | kObjCPointerPointee=(1<<1), |
| 24 | kReferencePointee=(1<<2), |
| 25 | kArrayElement=(1<<3), |
| 26 | kUnqualifiedDesugaredType=(1<<4), |
| 27 | kBaseClass=(1<<5), |
| 28 | kVirtualBaseClass=(1<<6), |
| 29 | kField=(1<<7), |
| 30 | kTemplateArgument=(1<<8), |
| 31 | }; |
| 32 | |
| 33 | constexprInductionRuleoperator|(InductionRule a,InductionRule b){ |
| 34 | returnstatic_cast<InductionRule>(static_cast<unsigned>(a)| |
| 35 | static_cast<unsigned>(b)); |
| 36 | } |
| 37 | constexprInductionRuleoperator&(InductionRule a,InductionRule b){ |
| 38 | returnstatic_cast<InductionRule>(static_cast<unsigned>(a)& |
| 39 | static_cast<unsigned>(b)); |
| 40 | } |
| 41 | |
| 42 | // Represents a match result |verdict_|. |
| 43 | // - MatchResult::kNoMatch: no match found against |type|. |
| 44 | // - MatchResult::kMatch: a match found against |type|. |
| 45 | // - MatchResult::kUndetermined: This denotes the result |
| 46 | // is not yet determined, due to cross references. |
| 47 | // Holds some additional information to tell reasons. |
| 48 | classMatchResult{ |
| 49 | public: |
| 50 | enumVerdict{ |
| 51 | kMatch, |
| 52 | kNoMatch, |
| 53 | // This denotes the match status is not yet determined. |
| 54 | kUndetermined, |
| 55 | }; |
| 56 | |
| 57 | explicitMatchResult(const clang::Type* type): type_(type){} |
| 58 | explicitMatchResult(const clang::Type* type,Verdict verdict) |
| 59 | : type_(type), verdict_(verdict){} |
| 60 | |
| 61 | const clang::Type* type()const{return type_;} |
| 62 | |
| 63 | Verdict verdict()const{returnthis->verdict_;} |
| 64 | |
| 65 | std::shared_ptr<MatchResult> source()const{returnthis->source_;} |
| 66 | |
| 67 | std::optional<clang::SourceLocation> source_loc()const{ |
| 68 | returnthis->source_loc_; |
| 69 | } |
| 70 | |
| 71 | private: |
| 72 | template<InductionRuleRules> |
| 73 | friendclassTypePredicate; |
| 74 | |
| 75 | // Merges a sub verdict into this type's verdict. |
| 76 | // |
| 77 | // | this \ sub | kNoMatch | kUndetermined | kMatch | |
| 78 | // +---------------+---------------+---------------+--------+ |
| 79 | // | kNoMatch | kNoMatch | kUndetermined | kMatch | |
| 80 | // | kUndetermined | kUndetermined | kUndetermined | kMatch | |
| 81 | // | kMatch | kMatch | kMatch | kMatch | |
| 82 | VerdictMergeSubResult( |
| 83 | std::shared_ptr<MatchResult>sub, |
| 84 | std::optional<clang::SourceLocation> loc= std::nullopt){ |
| 85 | if(sub->verdict_== kMatch&&this->verdict_!= kMatch){ |
| 86 | this->verdict_= kMatch; |
| 87 | this->source_= std::move(sub); |
| 88 | this->source_loc_= loc; |
| 89 | }elseif(sub->verdict_== kUndetermined&&this->verdict_== kNoMatch){ |
| 90 | this->verdict_= kUndetermined; |
| 91 | this->source_= std::move(sub); |
| 92 | this->source_loc_= loc; |
| 93 | } |
| 94 | returnthis->verdict_; |
| 95 | } |
| 96 | |
| 97 | // |type_| is considered to be |verdict_|. |
| 98 | // Optionally, the result contains a reason for the verdict, |source_|. |
| 99 | // There can be multiple reasons (e.g. |type_| has multiple matching |
| 100 | // members), but only one of them is stored. The relation between |type_| |
| 101 | // and |source_| is optionally shown at |source_loc_|. |
| 102 | const clang::Type* type_; |
| 103 | Verdict verdict_= kNoMatch; |
| 104 | std::shared_ptr<MatchResult> source_; |
| 105 | std::optional<clang::SourceLocation> source_loc_; |
| 106 | }; |
| 107 | |
| 108 | // Determines there is a match against |type| or not. |
| 109 | // A type is considered match if |IsBaseMatch| returns true or |
| 110 | // reach such |type| by applying InductionRule recursively. |
| 111 | template<InductionRuleRules> |
| 112 | classTypePredicate{ |
| 113 | public: |
| 114 | virtual~TypePredicate()=default; |
| 115 | boolMatches(const clang::Type* type)const{ |
| 116 | returnGetMatchResult(type)->verdict_==MatchResult::kMatch; |
| 117 | } |
| 118 | |
| 119 | std::shared_ptr<MatchResult>GetMatchResult( |
| 120 | const clang::Type* type, |
| 121 | std::set<const clang::Type*>* visited=nullptr)const{ |
| 122 | // Retrieve a "base" type to reduce recursion depth. |
| 123 | const clang::Type* raw_type=GetBaseType(type); |
| 124 | if(!raw_type||!raw_type->isRecordType()){ |
| 125 | // |TypePredicate| does not support followings: |
| 126 | // - function type |
| 127 | // - enum type |
| 128 | // - builtin type |
| 129 | // - complex type |
| 130 | // - obj-C types |
| 131 | // - using type |
| 132 | // - typeof type |
| 133 | return std::make_shared<MatchResult>(type);// No match. |
| 134 | } |
| 135 | |
| 136 | // Use a memoized result if exists. |
| 137 | auto iter= cache_.find(type); |
| 138 | if(iter!= cache_.end()){ |
| 139 | return iter->second; |
| 140 | } |
| 141 | |
| 142 | // This performs DFS on a directed graph composed of |Type*|. |
| 143 | // Avoid searching for visited nodes by managing |visited|, as this can lead |
| 144 | // to infinite loops in the presence of self-references and |
| 145 | // cross-references. Since finding a match for |Type* x| is equivalent to |
| 146 | // being able to reach from node |Type* x| to node |Type* y| where |
| 147 | // |IsBaseCase(y)|, there is no need to look up visited nodes again. |
| 148 | bool root= visited==nullptr; |
| 149 | if(root){ |
| 150 | // Will be deleted as a part of |clean_up()|. |
| 151 | visited=new std::set<const clang::Type*>(); |
| 152 | }elseif(visited->count(type)){ |
| 153 | // This type is already visited but not memoized, |
| 154 | // therefore this node is reached by following cross-references from |
| 155 | // ancestors. The verdict of this node cannot be determined without |
| 156 | // waiting for computation in its ancestors. |
| 157 | return std::make_shared<MatchResult>(raw_type, |
| 158 | MatchResult::kUndetermined); |
| 159 | } |
| 160 | visited->insert(type); |
| 161 | |
| 162 | auto match= std::make_shared<MatchResult>(raw_type); |
| 163 | |
| 164 | // Clean-up: this lambda is called automatically at the scope exit. |
| 165 | constauto clean_up= |
| 166 | llvm::make_scope_exit([this,&visited,&raw_type,&root,&match]{ |
| 167 | if(root){ |
| 168 | delete visited; |
| 169 | } |
| 170 | // Memoize the result if finalized. |
| 171 | if(match->verdict_!=MatchResult::kUndetermined){ |
| 172 | this->cache_.insert({raw_type, match}); |
| 173 | } |
| 174 | }); |
| 175 | |
| 176 | // Base case. |
| 177 | if(IsBaseMatch(raw_type)){ |
| 178 | match->verdict_=MatchResult::kMatch; |
| 179 | return match; |
| 180 | } |
| 181 | |
| 182 | const clang::RecordDecl* decl= raw_type->getAsRecordDecl(); |
| 183 | assert(decl); |
| 184 | |
| 185 | // Check member fields |
| 186 | ifconstexpr((Rules&InductionRule::kField)!=InductionRule::kNone){ |
| 187 | for(constauto& field: decl->fields()){ |
| 188 | match->MergeSubResult( |
| 189 | GetMatchResult(field->getType().getTypePtrOrNull(), visited), |
| 190 | field->getBeginLoc()); |
| 191 | |
| 192 | // Verdict finalized: early return. |
| 193 | if(match->verdict_==MatchResult::kMatch){ |
| 194 | return match; |
| 195 | } |
| 196 | } |
| 197 | } |
| 198 | |
| 199 | constauto* cxx_decl= clang::dyn_cast<clang::CXXRecordDecl>(decl); |
| 200 | if(cxx_decl&& cxx_decl->hasDefinition()){ |
| 201 | // Check base classes |
| 202 | ifconstexpr((Rules&InductionRule::kBaseClass)!= |
| 203 | InductionRule::kNone){ |
| 204 | for(constauto& base_specifier: cxx_decl->bases()){ |
| 205 | match->MergeSubResult( |
| 206 | GetMatchResult(base_specifier.getType().getTypePtr(), visited), |
| 207 | base_specifier.getBeginLoc()); |
| 208 | |
| 209 | // Verdict finalized: early return. |
| 210 | if(match->verdict_==MatchResult::kMatch){ |
| 211 | return match; |
| 212 | } |
| 213 | } |
| 214 | } |
| 215 | |
| 216 | // Check virtual base classes |
| 217 | ifconstexpr((Rules&InductionRule::kVirtualBaseClass)!= |
| 218 | InductionRule::kNone){ |
| 219 | for(constauto& base_specifier: cxx_decl->vbases()){ |
| 220 | match->MergeSubResult( |
| 221 | GetMatchResult(base_specifier.getType().getTypePtr(), visited), |
| 222 | base_specifier.getBeginLoc()); |
| 223 | |
| 224 | // Verdict finalized: early return. |
| 225 | if(match->verdict_==MatchResult::kMatch){ |
| 226 | return match; |
| 227 | } |
| 228 | } |
| 229 | } |
| 230 | } |
| 231 | |
| 232 | // Check template parameters. |
| 233 | ifconstexpr((Rules&InductionRule::kTemplateArgument)!= |
| 234 | InductionRule::kNone){ |
| 235 | if(auto* field_record_template= |
| 236 | clang::dyn_cast<clang::ClassTemplateSpecializationDecl>(decl)){ |
| 237 | constauto& template_args= field_record_template->getTemplateArgs(); |
| 238 | for(unsigned i=0; i< template_args.size(); i++){ |
| 239 | if(template_args[i].getKind()!= clang::TemplateArgument::Type){ |
| 240 | continue; |
| 241 | } |
| 242 | match->MergeSubResult( |
| 243 | GetMatchResult(template_args[i].getAsType().getTypePtrOrNull(), |
| 244 | visited), |
| 245 | field_record_template->getTemplateKeywordLoc()); |
| 246 | |
| 247 | // Verdict finalized: early return. |
| 248 | if(match->verdict_==MatchResult::kMatch){ |
| 249 | return match; |
| 250 | } |
| 251 | } |
| 252 | } |
| 253 | } |
| 254 | |
| 255 | // All reachable types have been traversed but the root type has not |
| 256 | // been marked as a match; therefore it must be no match. |
| 257 | if(root&& match->verdict_==MatchResult::kUndetermined){ |
| 258 | match->verdict_=MatchResult::kNoMatch; |
| 259 | } |
| 260 | return match; |
| 261 | } |
| 262 | |
| 263 | private: |
| 264 | const clang::Type*GetBaseType(const clang::Type* type)const{ |
| 265 | using clang::dyn_cast; |
| 266 | |
| 267 | const clang::Type* last_type=nullptr; |
| 268 | while(type&& type!= last_type){ |
| 269 | last_type= type; |
| 270 | |
| 271 | // Unwrap type aliases. |
| 272 | ifconstexpr((Rules&InductionRule::kUnqualifiedDesugaredType)!= |
| 273 | InductionRule::kNone){ |
| 274 | type= type->getUnqualifiedDesugaredType(); |
| 275 | } |
| 276 | |
| 277 | // Unwrap pointers. |
| 278 | ifconstexpr((Rules&InductionRule::kPointerPointee)!= |
| 279 | InductionRule::kNone){ |
| 280 | while(type&& type->isPointerType()){ |
| 281 | type= type->getPointeeType().getTypePtr(); |
| 282 | } |
| 283 | } |
| 284 | |
| 285 | // Unwrap ObjC pointers. |
| 286 | ifconstexpr((Rules&InductionRule::kObjCPointerPointee)!= |
| 287 | InductionRule::kNone){ |
| 288 | while(type&& type->isObjCObjectPointerType()){ |
| 289 | type= type->getPointeeType().getTypePtr(); |
| 290 | } |
| 291 | } |
| 292 | |
| 293 | // Unwrap array. |
| 294 | ifconstexpr((Rules&InductionRule::kArrayElement)!= |
| 295 | InductionRule::kNone){ |
| 296 | while(constauto* array_type= dyn_cast<clang::ArrayType>(type)){ |
| 297 | type= array_type->getElementType().getTypePtr(); |
| 298 | } |
| 299 | } |
| 300 | |
| 301 | // Unwrap reference. |
| 302 | ifconstexpr((Rules&InductionRule::kReferencePointee)!= |
| 303 | InductionRule::kNone){ |
| 304 | if(constauto* ref_type= dyn_cast<clang::ReferenceType>(type)){ |
| 305 | type= ref_type->getPointeeType().getTypePtrOrNull(); |
| 306 | } |
| 307 | } |
| 308 | } |
| 309 | return type; |
| 310 | } |
| 311 | |
| 312 | virtualboolIsBaseMatch(const clang::Type* type)const{returnfalse;} |
| 313 | |
| 314 | // Cache to efficiently determine match. |
| 315 | mutable std::map<const clang::Type*, std::shared_ptr<MatchResult>> cache_; |
| 316 | }; |
| 317 | |
| 318 | #endif// TOOLS_CLANG_PLUGINS_TYPEPREDICATEUTIL_H_ |