| // Copyright 2023 The Chromium Authors |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef TOOLS_CLANG_PLUGINS_TYPEPREDICATEUTIL_H_ |
| #define TOOLS_CLANG_PLUGINS_TYPEPREDICATEUTIL_H_ |
| |
| #include<map> |
| #include<memory> |
| #include<optional> |
| #include<set> |
| #include<string> |
| #include<vector> |
| |
| #include"clang/AST/Decl.h" |
| #include"clang/AST/DeclTemplate.h" |
| #include"clang/AST/Type.h" |
| #include"llvm/ADT/ScopeExit.h" |
| |
| enumclassInductionRule:unsigned{ |
| kNone=0, |
| kPointerPointee=(1<<0), |
| kObjCPointerPointee=(1<<1), |
| kReferencePointee=(1<<2), |
| kArrayElement=(1<<3), |
| kUnqualifiedDesugaredType=(1<<4), |
| kBaseClass=(1<<5), |
| kVirtualBaseClass=(1<<6), |
| kField=(1<<7), |
| kTemplateArgument=(1<<8), |
| }; |
| |
| constexprInductionRuleoperator|(InductionRule a,InductionRule b){ |
| returnstatic_cast<InductionRule>(static_cast<unsigned>(a)| |
| static_cast<unsigned>(b)); |
| } |
| constexprInductionRuleoperator&(InductionRule a,InductionRule b){ |
| returnstatic_cast<InductionRule>(static_cast<unsigned>(a)& |
| static_cast<unsigned>(b)); |
| } |
| |
| // Represents a match result |verdict_|. |
| // - MatchResult::kNoMatch: no match found against |type|. |
| // - MatchResult::kMatch: a match found against |type|. |
| // - MatchResult::kUndetermined: This denotes the result |
| // is not yet determined, due to cross references. |
| // Holds some additional information to tell reasons. |
| classMatchResult{ |
| public: |
| enumVerdict{ |
| kMatch, |
| kNoMatch, |
| // This denotes the match status is not yet determined. |
| kUndetermined, |
| }; |
| |
| explicitMatchResult(const clang::Type* type): type_(type){} |
| explicitMatchResult(const clang::Type* type,Verdict verdict) |
| : type_(type), verdict_(verdict){} |
| |
| const clang::Type* type()const{return type_;} |
| |
| Verdict verdict()const{returnthis->verdict_;} |
| |
| std::shared_ptr<MatchResult> source()const{returnthis->source_;} |
| |
| std::optional<clang::SourceLocation> source_loc()const{ |
| returnthis->source_loc_; |
| } |
| |
| private: |
| template<InductionRuleRules> |
| friendclassTypePredicate; |
| |
| // Merges a sub verdict into this type's verdict. |
| // |
| // | this \ sub | kNoMatch | kUndetermined | kMatch | |
| // +---------------+---------------+---------------+--------+ |
| // | kNoMatch | kNoMatch | kUndetermined | kMatch | |
| // | kUndetermined | kUndetermined | kUndetermined | kMatch | |
| // | kMatch | kMatch | kMatch | kMatch | |
| VerdictMergeSubResult( |
| std::shared_ptr<MatchResult>sub, |
| std::optional<clang::SourceLocation> loc= std::nullopt){ |
| if(sub->verdict_== kMatch&&this->verdict_!= kMatch){ |
| this->verdict_= kMatch; |
| this->source_= std::move(sub); |
| this->source_loc_= loc; |
| }elseif(sub->verdict_== kUndetermined&&this->verdict_== kNoMatch){ |
| this->verdict_= kUndetermined; |
| this->source_= std::move(sub); |
| this->source_loc_= loc; |
| } |
| returnthis->verdict_; |
| } |
| |
| // |type_| is considered to be |verdict_|. |
| // Optionally, the result contains a reason for the verdict, |source_|. |
| // There can be multiple reasons (e.g. |type_| has multiple matching |
| // members), but only one of them is stored. The relation between |type_| |
| // and |source_| is optionally shown at |source_loc_|. |
| const clang::Type* type_; |
| Verdict verdict_= kNoMatch; |
| std::shared_ptr<MatchResult> source_; |
| std::optional<clang::SourceLocation> source_loc_; |
| }; |
| |
| // Determines there is a match against |type| or not. |
| // A type is considered match if |IsBaseMatch| returns true or |
| // reach such |type| by applying InductionRule recursively. |
| template<InductionRuleRules> |
| classTypePredicate{ |
| public: |
| virtual~TypePredicate()=default; |
| boolMatches(const clang::Type* type)const{ |
| returnGetMatchResult(type)->verdict_==MatchResult::kMatch; |
| } |
| |
| std::shared_ptr<MatchResult>GetMatchResult( |
| const clang::Type* type, |
| std::set<const clang::Type*>* visited=nullptr)const{ |
| // Retrieve a "base" type to reduce recursion depth. |
| const clang::Type* raw_type=GetBaseType(type); |
| if(!raw_type||!raw_type->isRecordType()){ |
| // |TypePredicate| does not support followings: |
| // - function type |
| // - enum type |
| // - builtin type |
| // - complex type |
| // - obj-C types |
| // - using type |
| // - typeof type |
| return std::make_shared<MatchResult>(type);// No match. |
| } |
| |
| // Use a memoized result if exists. |
| auto iter= cache_.find(type); |
| if(iter!= cache_.end()){ |
| return iter->second; |
| } |
| |
| // This performs DFS on a directed graph composed of |Type*|. |
| // Avoid searching for visited nodes by managing |visited|, as this can lead |
| // to infinite loops in the presence of self-references and |
| // cross-references. Since finding a match for |Type* x| is equivalent to |
| // being able to reach from node |Type* x| to node |Type* y| where |
| // |IsBaseCase(y)|, there is no need to look up visited nodes again. |
| bool root= visited==nullptr; |
| if(root){ |
| // Will be deleted as a part of |clean_up()|. |
| visited=new std::set<const clang::Type*>(); |
| }elseif(visited->count(type)){ |
| // This type is already visited but not memoized, |
| // therefore this node is reached by following cross-references from |
| // ancestors. The verdict of this node cannot be determined without |
| // waiting for computation in its ancestors. |
| return std::make_shared<MatchResult>(raw_type, |
| MatchResult::kUndetermined); |
| } |
| visited->insert(type); |
| |
| auto match= std::make_shared<MatchResult>(raw_type); |
| |
| // Clean-up: this lambda is called automatically at the scope exit. |
| constauto clean_up= |
| llvm::make_scope_exit([this,&visited,&raw_type,&root,&match]{ |
| if(root){ |
| delete visited; |
| } |
| // Memoize the result if finalized. |
| if(match->verdict_!=MatchResult::kUndetermined){ |
| this->cache_.insert({raw_type, match}); |
| } |
| }); |
| |
| // Base case. |
| if(IsBaseMatch(raw_type)){ |
| match->verdict_=MatchResult::kMatch; |
| return match; |
| } |
| |
| const clang::RecordDecl* decl= raw_type->getAsRecordDecl(); |
| assert(decl); |
| |
| // Check member fields |
| ifconstexpr((Rules&InductionRule::kField)!=InductionRule::kNone){ |
| for(constauto& field: decl->fields()){ |
| match->MergeSubResult( |
| GetMatchResult(field->getType().getTypePtrOrNull(), visited), |
| field->getBeginLoc()); |
| |
| // Verdict finalized: early return. |
| if(match->verdict_==MatchResult::kMatch){ |
| return match; |
| } |
| } |
| } |
| |
| constauto* cxx_decl= clang::dyn_cast<clang::CXXRecordDecl>(decl); |
| if(cxx_decl&& cxx_decl->hasDefinition()){ |
| // Check base classes |
| ifconstexpr((Rules&InductionRule::kBaseClass)!= |
| InductionRule::kNone){ |
| for(constauto& base_specifier: cxx_decl->bases()){ |
| match->MergeSubResult( |
| GetMatchResult(base_specifier.getType().getTypePtr(), visited), |
| base_specifier.getBeginLoc()); |
| |
| // Verdict finalized: early return. |
| if(match->verdict_==MatchResult::kMatch){ |
| return match; |
| } |
| } |
| } |
| |
| // Check virtual base classes |
| ifconstexpr((Rules&InductionRule::kVirtualBaseClass)!= |
| InductionRule::kNone){ |
| for(constauto& base_specifier: cxx_decl->vbases()){ |
| match->MergeSubResult( |
| GetMatchResult(base_specifier.getType().getTypePtr(), visited), |
| base_specifier.getBeginLoc()); |
| |
| // Verdict finalized: early return. |
| if(match->verdict_==MatchResult::kMatch){ |
| return match; |
| } |
| } |
| } |
| } |
| |
| // Check template parameters. |
| ifconstexpr((Rules&InductionRule::kTemplateArgument)!= |
| InductionRule::kNone){ |
| if(auto* field_record_template= |
| clang::dyn_cast<clang::ClassTemplateSpecializationDecl>(decl)){ |
| constauto& template_args= field_record_template->getTemplateArgs(); |
| for(unsigned i=0; i< template_args.size(); i++){ |
| if(template_args[i].getKind()!= clang::TemplateArgument::Type){ |
| continue; |
| } |
| match->MergeSubResult( |
| GetMatchResult(template_args[i].getAsType().getTypePtrOrNull(), |
| visited), |
| field_record_template->getTemplateKeywordLoc()); |
| |
| // Verdict finalized: early return. |
| if(match->verdict_==MatchResult::kMatch){ |
| return match; |
| } |
| } |
| } |
| } |
| |
| // All reachable types have been traversed but the root type has not |
| // been marked as a match; therefore it must be no match. |
| if(root&& match->verdict_==MatchResult::kUndetermined){ |
| match->verdict_=MatchResult::kNoMatch; |
| } |
| return match; |
| } |
| |
| private: |
| const clang::Type*GetBaseType(const clang::Type* type)const{ |
| using clang::dyn_cast; |
| |
| const clang::Type* last_type=nullptr; |
| while(type&& type!= last_type){ |
| last_type= type; |
| |
| // Unwrap type aliases. |
| ifconstexpr((Rules&InductionRule::kUnqualifiedDesugaredType)!= |
| InductionRule::kNone){ |
| type= type->getUnqualifiedDesugaredType(); |
| } |
| |
| // Unwrap pointers. |
| ifconstexpr((Rules&InductionRule::kPointerPointee)!= |
| InductionRule::kNone){ |
| while(type&& type->isPointerType()){ |
| type= type->getPointeeType().getTypePtr(); |
| } |
| } |
| |
| // Unwrap ObjC pointers. |
| ifconstexpr((Rules&InductionRule::kObjCPointerPointee)!= |
| InductionRule::kNone){ |
| while(type&& type->isObjCObjectPointerType()){ |
| type= type->getPointeeType().getTypePtr(); |
| } |
| } |
| |
| // Unwrap array. |
| ifconstexpr((Rules&InductionRule::kArrayElement)!= |
| InductionRule::kNone){ |
| while(constauto* array_type= dyn_cast<clang::ArrayType>(type)){ |
| type= array_type->getElementType().getTypePtr(); |
| } |
| } |
| |
| // Unwrap reference. |
| ifconstexpr((Rules&InductionRule::kReferencePointee)!= |
| InductionRule::kNone){ |
| if(constauto* ref_type= dyn_cast<clang::ReferenceType>(type)){ |
| type= ref_type->getPointeeType().getTypePtrOrNull(); |
| } |
| } |
| } |
| return type; |
| } |
| |
| virtualboolIsBaseMatch(const clang::Type* type)const{returnfalse;} |
| |
| // Cache to efficiently determine match. |
| mutable std::map<const clang::Type*, std::shared_ptr<MatchResult>> cache_; |
| }; |
| |
| #endif// TOOLS_CLANG_PLUGINS_TYPEPREDICATEUTIL_H_ |
