For Loop Conversion
[lldb.git] / clang-tools-extra / loop-convert / LoopMatchers.cpp
1 #include "LoopMatchers.h"
2
3 namespace clang {
4 namespace loop_migrate {
5
6 using namespace clang::ast_matchers;
7 const char LoopName[] = "forLoop";
8 const char ConditionBoundName[] = "conditionBound";
9 const char ConditionVarName[] = "conditionVar";
10 const char IncrementVarName[] = "incrementVar";
11 const char InitVarName[] = "initVar";
12 const char EndCallName[] = "endCall";
13 const char ConditionEndVarName[] = "conditionEndVar";
14 const char EndVarName[] = "endVar";
15
16 static const TypeMatcher AnyType = anything();
17
18 // FIXME: How best to document complicated matcher expressions? They're fairly
19 // self-documenting...but there may be some unintuitive parts.
20
21 /// \brief The matcher for loops over arrays.
22 ///
23 /// In this general example, assuming 'j' and 'k' are of integral type:
24 ///   for (int i = 0; j < 3 + 2; ++k) { ... }
25 /// The following string identifers are bound to the parts of the AST:
26 ///   ConditionVarName: 'j' (as a VarDecl)
27 ///   ConditionBoundName: '3 + 2' (as an Expr)
28 ///   InitVarName: 'i' (as a VarDecl)
29 ///   IncrementVarName: 'k' (as a VarDecl)
30 ///   LoopName: The entire for loop (as a ForStmt)
31 ///
32 /// Client code will need to make sure that:
33 ///   - The three index variables identified by the matcher are the same
34 ///     VarDecl.
35 ///   - The index variable is only used as an array index.
36 ///   - All arrays indexed by the loop are the same.
37 StatementMatcher makeArrayLoopMatcher() {
38   StatementMatcher ArrayComparisonMatcher =
39       expression(ignoringParenImpCasts(declarationReference(to(
40           variable(hasType(isInteger())).bind(ConditionVarName)))));
41   StatementMatcher ArrayBoundMatcher =
42       expression(hasType(isInteger())).bind(ConditionBoundName);
43
44   return id(LoopName, forStmt(
45       hasLoopInit(declarationStatement(hasSingleDecl(id(InitVarName, variable(
46           hasInitializer(ignoringParenImpCasts(integerLiteral(equals(0))))))))),
47       hasCondition(anyOf(binaryOperator(hasOperatorName("<"),
48                                         hasLHS(ArrayComparisonMatcher),
49                                         hasRHS(ArrayBoundMatcher)),
50                          binaryOperator(hasOperatorName(">"),
51                                         hasLHS(ArrayBoundMatcher),
52                                         hasRHS(ArrayComparisonMatcher)))),
53       hasIncrement(unaryOperator(
54           hasOperatorName("++"),
55           hasUnaryOperand(declarationReference(to(
56               variable(hasType(isInteger())).bind(IncrementVarName))))))));
57 }
58
59 /// \brief The matcher used for iterator-based for loops.
60 ///
61 /// This matcher is more flexible than array-based loops. It will match
62 /// catch loops of the following textual forms (regardless of whether the
63 /// iterator type is actually a pointer type or a class type):
64 ///
65 /// Assuming f, g, and h are of type containerType::iterator,
66 ///   for (containerType::iterator it = container.begin(),
67 ///        e = createIterator(); f != g; ++h) { ... }
68 ///   for (containerType::iterator it = container.begin();
69 ///        f != anotherContainer.end(); ++h) { ... }
70 /// The following string identifiers are bound to the parts of the AST:
71 ///   InitVarName: 'it' (as a VarDecl)
72 ///   ConditionVarName: 'f' (as a VarDecl)
73 ///   LoopName: The entire for loop (as a ForStmt)
74 ///   In the first example only:
75 ///     EndVarName: 'e' (as a VarDecl)
76 ///     ConditionEndVarName: 'g' (as a VarDecl)
77 ///   In the second example only:
78 ///     EndCallName: 'container.end()' (as a CXXMemberCallExpr)
79 ///
80 /// Client code will need to make sure that:
81 ///   - The iterator variables 'it', 'f', and 'h' are the same
82 ///   - The two containers on which 'begin' and 'end' are called are the same
83 ///   - If the end iterator variable 'g' is defined, it is the same as 'f'
84 StatementMatcher makeIteratorLoopMatcher() {
85   StatementMatcher BeginCallMatcher =
86       memberCall(argumentCountIs(0), callee(method(hasName("begin"))));
87
88   DeclarationMatcher InitDeclMatcher =
89       variable(hasInitializer(anything())).bind(InitVarName);
90
91   DeclarationMatcher EndDeclMatcher =
92       variable(hasInitializer(anything())).bind(EndVarName);
93
94   StatementMatcher EndCallMatcher =
95       memberCall(argumentCountIs(0), callee(method(hasName("end"))));
96
97   StatementMatcher IteratorBoundMatcher =
98       expression(anyOf(ignoringParenImpCasts(declarationReference(to(
99           variable().bind(ConditionEndVarName)))),
100                        ignoringParenImpCasts(
101                            expression(EndCallMatcher).bind(EndCallName)),
102                        materializeTempExpr(
103                            ignoringParenImpCasts(
104                                expression(EndCallMatcher).bind(EndCallName)))));
105
106   StatementMatcher IteratorComparisonMatcher =
107       expression(ignoringParenImpCasts(declarationReference(to(
108           variable().bind(ConditionVarName)))));
109
110   StatementMatcher OverloadedNEQMatcher = overloadedOperatorCall(
111       hasOverloadedOperatorName("!="),
112       argumentCountIs(2),
113       hasArgument(0, IteratorComparisonMatcher),
114       hasArgument(1, IteratorBoundMatcher));
115
116   return id(LoopName, forStmt(
117             hasLoopInit(anyOf(
118                 declarationStatement(declCountIs(2),
119                                      containsDeclaration(0, InitDeclMatcher),
120                                      containsDeclaration(1, EndDeclMatcher)),
121                 declarationStatement(hasSingleDecl(InitDeclMatcher)))),
122             hasCondition(anyOf(
123                 binaryOperator(hasOperatorName("!="),
124                                hasLHS(IteratorComparisonMatcher),
125                                hasRHS(IteratorBoundMatcher)),
126                 binaryOperator(hasOperatorName("!="),
127                                hasLHS(IteratorBoundMatcher),
128                                hasRHS(IteratorComparisonMatcher)),
129                 OverloadedNEQMatcher)),
130             hasIncrement(anyOf(
131                 unaryOperator(hasOperatorName("++"),
132                               hasUnaryOperand(declarationReference(to(
133                                   variable(hasType(pointsTo(AnyType)))
134                                      .bind(IncrementVarName))))),
135                 overloadedOperatorCall(
136                     hasOverloadedOperatorName("++"),
137                     hasArgument(0, declarationReference(to(
138                         variable().bind(IncrementVarName)))))))));
139 }
140
141 /// \brief The matcher used for array-like containers (pseudoarrays).
142 ///
143 /// This matcher is more flexible than array-based loops. It will match
144 /// loops of the following textual forms (regardless of whether the
145 /// iterator type is actually a pointer type or a class type):
146 ///
147 /// Assuming f, g, and h are of type containerType::iterator,
148 ///   for (int i = 0, j = container.size(); f < g; ++h) { ... }
149 ///   for (int i = 0; f < container.size(); ++h) { ... }
150 /// The following string identifiers are bound to the parts of the AST:
151 ///   InitVarName: 'i' (as a VarDecl)
152 ///   ConditionVarName: 'f' (as a VarDecl)
153 ///   LoopName: The entire for loop (as a ForStmt)
154 ///   In the first example only:
155 ///     EndVarName: 'j' (as a VarDecl)
156 ///     ConditionEndVarName: 'g' (as a VarDecl)
157 ///   In the second example only:
158 ///     EndCallName: 'container.size()' (as a CXXMemberCallExpr)
159 ///
160 /// Client code will need to make sure that:
161 ///   - The index variables 'i', 'f', and 'h' are the same
162 ///   - The containers on which 'size()' is called is the container indexed
163 ///   - The index variable is only used in overloaded operator[] or
164 ///     container.at()
165 ///   - If the end iterator variable 'g' is defined, it is the same as 'j'
166 ///   - The container's iterators would not be invalidated during the loop
167 StatementMatcher makePseudoArrayLoopMatcher() {
168   DeclarationMatcher InitDeclMatcher =
169          variable(hasInitializer(ignoringParenImpCasts(
170              integerLiteral(equals(0))))).bind(InitVarName);
171   StatementMatcher SizeCallMatcher =
172       memberCall(argumentCountIs(0), callee(method(anyOf(hasName("size"),
173                                                          hasName("length")))));
174
175   StatementMatcher EndInitMatcher =
176       expression(anyOf(
177           ignoringParenImpCasts(expression(SizeCallMatcher).bind(EndCallName)),
178           explicitCast(hasSourceExpression(ignoringParenImpCasts(
179               expression(SizeCallMatcher).bind(EndCallName))))));
180
181   DeclarationMatcher EndDeclMatcher =
182        variable(hasInitializer(EndInitMatcher)).bind(EndVarName);
183
184   StatementMatcher IntegerComparisonMatcher =
185       expression(ignoringParenImpCasts(declarationReference(to(
186           variable(hasType(isInteger())).bind(ConditionVarName)))));
187
188   StatementMatcher ArrayBoundMatcher =
189       expression(anyOf(
190           ignoringParenImpCasts(declarationReference(to(
191               variable(hasType(isInteger())).bind(ConditionEndVarName)))),
192           EndInitMatcher));
193
194   return id(LoopName, forStmt(
195       hasLoopInit(anyOf(
196           declarationStatement(declCountIs(2),
197                                containsDeclaration(0, InitDeclMatcher),
198                                containsDeclaration(1, EndDeclMatcher)),
199           declarationStatement(hasSingleDecl(InitDeclMatcher)))),
200       hasCondition(anyOf(
201           binaryOperator(hasOperatorName("<"),
202                          hasLHS(IntegerComparisonMatcher),
203                          hasRHS(ArrayBoundMatcher)),
204           binaryOperator(hasOperatorName(">"),
205                          hasLHS(ArrayBoundMatcher),
206                          hasRHS(IntegerComparisonMatcher)))),
207       hasIncrement(unaryOperator(
208           hasOperatorName("++"),
209           hasUnaryOperand(declarationReference(to(
210               variable(hasType(isInteger())).bind(IncrementVarName))))))));
211 }
212
213 } // namespace loop_migrate
214 } // namespace clang