1 // RUN: %check_clang_tidy %s performance-inefficient-vector-operation %t -- \ 2 // RUN: -format-style=llvm \ 3 // RUN: -config='{CheckOptions: \ 4 // RUN: [{key: performance-inefficient-vector-operation.EnableProto, value: true}]}' 5 6 namespace std { 7 8 typedef int size_t; 9 10 template<class E> class initializer_list { 11 public: 12 using value_type = E; 13 using reference = E&; 14 using const_reference = const E&; 15 using size_type = size_t; 16 using iterator = const E*; 17 using const_iterator = const E*; 18 initializer_list(); 19 size_t size() const; // number of elements 20 const E* begin() const; // first element 21 const E* end() const; // one past the last element 22 }; 23 24 // initializer list range access 25 template<class E> const E* begin(initializer_list<E> il); 26 template<class E> const E* end(initializer_list<E> il); 27 28 template <class T> 29 class vector { 30 public: 31 typedef T* iterator; 32 typedef const T* const_iterator; 33 typedef T& reference; 34 typedef const T& const_reference; 35 typedef size_t size_type; 36 37 explicit vector(); 38 explicit vector(size_type n); 39 40 void push_back(const T& val); 41 42 template <class... Args> void emplace_back(Args &&... args); 43 44 void reserve(size_t n); 45 void resize(size_t n); 46 47 size_t size(); 48 const_reference operator[] (size_type) const; 49 reference operator[] (size_type); 50 51 const_iterator begin() const; 52 const_iterator end() const; 53 }; 54 } // namespace std 55 56 class Foo { 57 public: 58 explicit Foo(int); 59 }; 60 61 class Bar { 62 public: 63 Bar(int); 64 }; 65 66 int Op(int); 67 68 namespace proto2 { 69 class MessageLite {}; 70 class Message : public MessageLite {}; 71 } // namespace proto2 72 73 class FooProto : public proto2::Message { 74 public: 75 int *add_x(); // repeated int x; 76 void add_x(int x); 77 void mutable_x(); 78 void mutable_y(); 79 int add_z() const; // optional int add_z; 80 }; 81 82 class BarProto : public proto2::Message { 83 public: 84 int *add_x(); 85 void add_x(int x); 86 void mutable_x(); 87 void mutable_y(); 88 }; 89 f(std::vector<int> & t)90void f(std::vector<int>& t) { 91 { 92 std::vector<int> v0; 93 // CHECK-FIXES: v0.reserve(10); 94 for (int i = 0; i < 10; ++i) 95 v0.push_back(i); 96 // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called inside a loop; consider pre-allocating the container capacity before the loop 97 } 98 { 99 std::vector<int> v1; 100 // CHECK-FIXES: v1.reserve(10); 101 for (int i = 0; i < 10; i++) 102 v1.push_back(i); 103 // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called 104 } 105 { 106 std::vector<int> v2; 107 // CHECK-FIXES: v2.reserve(10); 108 for (int i = 0; i < 10; ++i) 109 v2.push_back(0); 110 // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called 111 } 112 { 113 std::vector<int> v3; 114 // CHECK-FIXES: v3.reserve(5); 115 for (int i = 0; i < 5; ++i) { 116 v3.push_back(i); 117 // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called 118 } 119 // CHECK-FIXES-NOT: v3.reserve(10); 120 for (int i = 0; i < 10; ++i) { 121 // No fix for this loop as we encounter the prior loops. 122 v3.push_back(i); 123 } 124 } 125 { 126 std::vector<int> v4; 127 std::vector<int> v5; 128 v5.reserve(3); 129 // CHECK-FIXES: v4.reserve(10); 130 for (int i = 0; i < 10; ++i) 131 v4.push_back(i); 132 // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called 133 } 134 { 135 std::vector<int> v6; 136 // CHECK-FIXES: v6.reserve(t.size()); 137 for (std::size_t i = 0; i < t.size(); ++i) { 138 v6.push_back(t[i]); 139 // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called 140 } 141 } 142 { 143 std::vector<int> v7; 144 // CHECK-FIXES: v7.reserve(t.size() - 1); 145 for (std::size_t i = 0; i < t.size() - 1; ++i) { 146 v7.push_back(t[i]); 147 } // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called 148 } 149 { 150 std::vector<int> v8; 151 // CHECK-FIXES: v8.reserve(t.size()); 152 for (const auto &e : t) { 153 v8.push_back(e); 154 // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called 155 } 156 } 157 { 158 std::vector<int> v9; 159 // CHECK-FIXES: v9.reserve(t.size()); 160 for (const auto &e : t) { 161 v9.push_back(Op(e)); 162 // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called 163 } 164 } 165 { 166 std::vector<Foo> v10; 167 // CHECK-FIXES: v10.reserve(t.size()); 168 for (const auto &e : t) { 169 v10.push_back(Foo(e)); 170 // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called 171 } 172 } 173 { 174 std::vector<Bar> v11; 175 // CHECK-FIXES: v11.reserve(t.size()); 176 for (const auto &e : t) { 177 v11.push_back(e); 178 // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called 179 } 180 } 181 { 182 std::vector<Foo> v12; 183 // CHECK-FIXES: v12.reserve(t.size()); 184 for (const auto &e : t) { 185 v12.emplace_back(e); 186 // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'emplace_back' is called 187 } 188 } 189 190 { 191 FooProto foo; 192 // CHECK-FIXES: foo.mutable_x()->Reserve(5); 193 for (int i = 0; i < 5; i++) { 194 foo.add_x(i); 195 // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'add_x' is called inside a loop; consider pre-allocating the container capacity before the loop 196 } 197 } 198 199 // ---- Non-fixed Cases ---- 200 { 201 std::vector<int> z0; 202 z0.reserve(20); 203 // CHECK-FIXES-NOT: z0.reserve(10); 204 // There is a "reserve" call already. 205 for (int i = 0; i < 10; ++i) { 206 z0.push_back(i); 207 } 208 } 209 { 210 std::vector<int> z1; 211 z1.reserve(5); 212 // CHECK-FIXES-NOT: z1.reserve(10); 213 // There is a "reserve" call already. 214 for (int i = 0; i < 10; ++i) { 215 z1.push_back(i); 216 } 217 } 218 { 219 std::vector<int> z2; 220 z2.resize(5); 221 // CHECK-FIXES-NOT: z2.reserve(10); 222 // There is a ref usage of v before the loop. 223 for (int i = 0; i < 10; ++i) { 224 z2.push_back(i); 225 } 226 } 227 { 228 std::vector<int> z3; 229 z3.push_back(0); 230 // CHECK-FIXES-NOT: z3.reserve(10); 231 // There is a ref usage of v before the loop. 232 for (int i = 0; i < 10; ++i) { 233 z3.push_back(i); 234 } 235 } 236 { 237 std::vector<int> z4; 238 f(z4); 239 // CHECK-FIXES-NOT: z4.reserve(10); 240 // There is a ref usage of z4 before the loop. 241 for (int i = 0; i < 10; ++i) { 242 z4.push_back(i); 243 } 244 } 245 { 246 std::vector<int> z5(20); 247 // CHECK-FIXES-NOT: z5.reserve(10); 248 // z5 is not constructed with default constructor. 249 for (int i = 0; i < 10; ++i) { 250 z5.push_back(i); 251 } 252 } 253 { 254 std::vector<int> z6; 255 // CHECK-FIXES-NOT: z6.reserve(10); 256 // For-loop is not started with 0. 257 for (int i = 1; i < 10; ++i) { 258 z6.push_back(i); 259 } 260 } 261 { 262 std::vector<int> z7; 263 // CHECK-FIXES-NOT: z7.reserve(t.size()); 264 // z7 isn't referenced in for-loop body. 265 for (std::size_t i = 0; i < t.size(); ++i) { 266 t.push_back(i); 267 } 268 } 269 { 270 std::vector<int> z8; 271 int k; 272 // CHECK-FIXES-NOT: z8.reserve(10); 273 // For-loop isn't a fixable loop. 274 for (std::size_t i = 0; k < 10; ++i) { 275 z8.push_back(t[i]); 276 } 277 } 278 { 279 std::vector<int> z9; 280 // CHECK-FIXES-NOT: z9.reserve(i + 1); 281 // The loop end expression refers to the loop variable i. 282 for (int i = 0; i < i + 1; i++) 283 z9.push_back(i); 284 } 285 { 286 std::vector<int> z10; 287 int k; 288 // CHECK-FIXES-NOT: z10.reserve(10); 289 // For-loop isn't a fixable loop. 290 for (std::size_t i = 0; i < 10; ++k) { 291 z10.push_back(t[i]); 292 } 293 } 294 { 295 std::vector<int> z11; 296 // initializer_list should not trigger the check. 297 for (int e : {1, 2, 3, 4, 5}) { 298 z11.push_back(e); 299 } 300 } 301 { 302 std::vector<int> z12; 303 std::vector<int>* z13 = &t; 304 // We only support detecting the range init expression which references 305 // container directly. 306 // Complex range init expressions like `*z13` is not supported. 307 for (const auto &e : *z13) { 308 z12.push_back(e); 309 } 310 } 311 312 { 313 FooProto foo; 314 foo.mutable_x(); 315 // CHECK-FIXES-NOT: foo.mutable_x()->Reserve(5); 316 for (int i = 0; i < 5; i++) { 317 foo.add_x(i); 318 } 319 } 320 { 321 FooProto foo; 322 // CHECK-FIXES-NOT: foo.mutable_x()->Reserve(5); 323 for (int i = 0; i < 5; i++) { 324 foo.add_x(i); 325 foo.add_x(i); 326 } 327 } 328 { 329 FooProto foo; 330 // CHECK-FIXES-NOT: foo.mutable_x()->Reserve(5); 331 foo.add_x(-1); 332 for (int i = 0; i < 5; i++) { 333 foo.add_x(i); 334 } 335 } 336 { 337 FooProto foo; 338 BarProto bar; 339 bar.mutable_x(); 340 // CHECK-FIXES-NOT: foo.mutable_x()->Reserve(5); 341 for (int i = 0; i < 5; i++) { 342 foo.add_x(); 343 bar.add_x(); 344 } 345 } 346 { 347 FooProto foo; 348 foo.mutable_y(); 349 // CHECK-FIXES-NOT: foo.mutable_x()->Reserve(5); 350 for (int i = 0; i < 5; i++) { 351 foo.add_x(i); 352 } 353 } 354 { 355 FooProto foo; 356 // CHECK-FIXES-NOT: foo.mutable_z()->Reserve(5); 357 for (int i = 0; i < 5; i++) { 358 foo.add_z(); 359 } 360 } 361 } 362