Movatterモバイル変換


[0]ホーム

URL:


Google Git
Sign in
chromium /chromium /src /main /. /tools /clang /plugins /TypePredicateUtil.h
blob: 85782641f5ba7df98112aa54f3d6caef88699293 [file] [log] [blame]
mikte6f6ec42023-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
20enumclassInductionRule: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
33constexprInductionRuleoperator|(InductionRule a,InductionRule b){
34returnstatic_cast<InductionRule>(static_cast<unsigned>(a)|
35static_cast<unsigned>(b));
36}
37constexprInductionRuleoperator&(InductionRule a,InductionRule b){
38returnstatic_cast<InductionRule>(static_cast<unsigned>(a)&
39static_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.
48classMatchResult{
49public:
50enumVerdict{
51 kMatch,
52 kNoMatch,
53// This denotes the match status is not yet determined.
54 kUndetermined,
55};
56
57explicitMatchResult(const clang::Type* type): type_(type){}
58explicitMatchResult(const clang::Type* type,Verdict verdict)
59: type_(type), verdict_(verdict){}
60
61const clang::Type* type()const{return type_;}
62
63Verdict verdict()const{returnthis->verdict_;}
64
65 std::shared_ptr<MatchResult> source()const{returnthis->source_;}
66
67 std::optional<clang::SourceLocation> source_loc()const{
68returnthis->source_loc_;
69}
70
71private:
72template<InductionRuleRules>
73friendclassTypePredicate;
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 |
82VerdictMergeSubResult(
83 std::shared_ptr<MatchResult>sub,
84 std::optional<clang::SourceLocation> loc= std::nullopt){
85if(sub->verdict_== kMatch&&this->verdict_!= kMatch){
86this->verdict_= kMatch;
87this->source_= std::move(sub);
88this->source_loc_= loc;
89}elseif(sub->verdict_== kUndetermined&&this->verdict_== kNoMatch){
90this->verdict_= kUndetermined;
91this->source_= std::move(sub);
92this->source_loc_= loc;
93}
94returnthis->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_|.
102const clang::Type* type_;
103Verdict 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.
111template<InductionRuleRules>
112classTypePredicate{
113public:
114virtual~TypePredicate()=default;
115boolMatches(const clang::Type* type)const{
116returnGetMatchResult(type)->verdict_==MatchResult::kMatch;
117}
118
119 std::shared_ptr<MatchResult>GetMatchResult(
120const clang::Type* type,
121 std::set<const clang::Type*>* visited=nullptr)const{
122// Retrieve a "base" type to reduce recursion depth.
123const clang::Type* raw_type=GetBaseType(type);
124if(!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
133return std::make_shared<MatchResult>(type);// No match.
134}
135
136// Use a memoized result if exists.
137auto iter= cache_.find(type);
138if(iter!= cache_.end()){
139return 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.
148bool root= visited==nullptr;
149if(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.
157return std::make_shared<MatchResult>(raw_type,
158MatchResult::kUndetermined);
159}
160 visited->insert(type);
161
162auto match= std::make_shared<MatchResult>(raw_type);
163
164// Clean-up: this lambda is called automatically at the scope exit.
165constauto clean_up=
166 llvm::make_scope_exit([this,&visited,&raw_type,&root,&match]{
167if(root){
168delete visited;
169}
170// Memoize the result if finalized.
171if(match->verdict_!=MatchResult::kUndetermined){
172this->cache_.insert({raw_type, match});
173}
174});
175
176// Base case.
177if(IsBaseMatch(raw_type)){
178 match->verdict_=MatchResult::kMatch;
179return match;
180}
181
182const clang::RecordDecl* decl= raw_type->getAsRecordDecl();
183assert(decl);
184
185// Check member fields
186ifconstexpr((Rules&InductionRule::kField)!=InductionRule::kNone){
187for(constauto& field: decl->fields()){
188 match->MergeSubResult(
189GetMatchResult(field->getType().getTypePtrOrNull(), visited),
190 field->getBeginLoc());
191
192// Verdict finalized: early return.
193if(match->verdict_==MatchResult::kMatch){
194return match;
195}
196}
197}
198
199constauto* cxx_decl= clang::dyn_cast<clang::CXXRecordDecl>(decl);
200if(cxx_decl&& cxx_decl->hasDefinition()){
201// Check base classes
202ifconstexpr((Rules&InductionRule::kBaseClass)!=
203InductionRule::kNone){
204for(constauto& base_specifier: cxx_decl->bases()){
205 match->MergeSubResult(
206GetMatchResult(base_specifier.getType().getTypePtr(), visited),
207 base_specifier.getBeginLoc());
208
209// Verdict finalized: early return.
210if(match->verdict_==MatchResult::kMatch){
211return match;
212}
213}
214}
215
216// Check virtual base classes
217ifconstexpr((Rules&InductionRule::kVirtualBaseClass)!=
218InductionRule::kNone){
219for(constauto& base_specifier: cxx_decl->vbases()){
220 match->MergeSubResult(
221GetMatchResult(base_specifier.getType().getTypePtr(), visited),
222 base_specifier.getBeginLoc());
223
224// Verdict finalized: early return.
225if(match->verdict_==MatchResult::kMatch){
226return match;
227}
228}
229}
230}
231
232// Check template parameters.
233ifconstexpr((Rules&InductionRule::kTemplateArgument)!=
234InductionRule::kNone){
235if(auto* field_record_template=
236 clang::dyn_cast<clang::ClassTemplateSpecializationDecl>(decl)){
237constauto& template_args= field_record_template->getTemplateArgs();
238for(unsigned i=0; i< template_args.size(); i++){
239if(template_args[i].getKind()!= clang::TemplateArgument::Type){
240continue;
241}
242 match->MergeSubResult(
243GetMatchResult(template_args[i].getAsType().getTypePtrOrNull(),
244 visited),
245 field_record_template->getTemplateKeywordLoc());
246
247// Verdict finalized: early return.
248if(match->verdict_==MatchResult::kMatch){
249return 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.
257if(root&& match->verdict_==MatchResult::kUndetermined){
258 match->verdict_=MatchResult::kNoMatch;
259}
260return match;
261}
262
263private:
264const clang::Type*GetBaseType(const clang::Type* type)const{
265using clang::dyn_cast;
266
267const clang::Type* last_type=nullptr;
268while(type&& type!= last_type){
269 last_type= type;
270
271// Unwrap type aliases.
272ifconstexpr((Rules&InductionRule::kUnqualifiedDesugaredType)!=
273InductionRule::kNone){
274 type= type->getUnqualifiedDesugaredType();
275}
276
277// Unwrap pointers.
278ifconstexpr((Rules&InductionRule::kPointerPointee)!=
279InductionRule::kNone){
280while(type&& type->isPointerType()){
281 type= type->getPointeeType().getTypePtr();
282}
283}
284
285// Unwrap ObjC pointers.
286ifconstexpr((Rules&InductionRule::kObjCPointerPointee)!=
287InductionRule::kNone){
288while(type&& type->isObjCObjectPointerType()){
289 type= type->getPointeeType().getTypePtr();
290}
291}
292
293// Unwrap array.
294ifconstexpr((Rules&InductionRule::kArrayElement)!=
295InductionRule::kNone){
296while(constauto* array_type= dyn_cast<clang::ArrayType>(type)){
297 type= array_type->getElementType().getTypePtr();
298}
299}
300
301// Unwrap reference.
302ifconstexpr((Rules&InductionRule::kReferencePointee)!=
303InductionRule::kNone){
304if(constauto* ref_type= dyn_cast<clang::ReferenceType>(type)){
305 type= ref_type->getPointeeType().getTypePtrOrNull();
306}
307}
308}
309return type;
310}
311
312virtualboolIsBaseMatch(const clang::Type* type)const{returnfalse;}
313
314// Cache to efficiently determine match.
315mutable std::map<const clang::Type*, std::shared_ptr<MatchResult>> cache_;
316};
317
318#endif// TOOLS_CLANG_PLUGINS_TYPEPREDICATEUTIL_H_

[8]ページ先頭

©2009-2025 Movatter.jp