1 //===--- UseRangesCheck.cpp - clang-tidy ----------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "UseRangesCheck.h" 10 #include "clang/AST/Decl.h" 11 #include "clang/Basic/Diagnostic.h" 12 #include "clang/Basic/LLVM.h" 13 #include "llvm/ADT/ArrayRef.h" 14 #include "llvm/ADT/IntrusiveRefCntPtr.h" 15 #include "llvm/ADT/SmallString.h" 16 #include "llvm/ADT/SmallVector.h" 17 #include "llvm/ADT/StringRef.h" 18 #include <initializer_list> 19 #include <optional> 20 #include <string> 21 22 // FixItHint - Let the docs script know that this class does provide fixits 23 24 namespace clang::tidy::boost { 25 26 namespace { 27 /// Base replacer that handles the boost include path and namespace 28 class BoostReplacer : public UseRangesCheck::Replacer { 29 public: 30 BoostReplacer(ArrayRef<UseRangesCheck::Signature> Signatures, 31 bool IncludeSystem) 32 : Signatures(Signatures), IncludeSystem(IncludeSystem) {} 33 34 ArrayRef<UseRangesCheck::Signature> getReplacementSignatures() const final { 35 return Signatures; 36 } 37 38 virtual std::pair<StringRef, StringRef> 39 getBoostName(const NamedDecl &OriginalName) const = 0; 40 41 virtual std::pair<StringRef, StringRef> 42 getBoostHeader(const NamedDecl &OriginalName) const = 0; 43 44 std::optional<std::string> 45 getReplaceName(const NamedDecl &OriginalName) const final { 46 auto [Namespace, Function] = getBoostName(OriginalName); 47 return ("boost::" + Namespace + (Namespace.empty() ? "" : "::") + Function) 48 .str(); 49 } 50 51 std::optional<std::string> 52 getHeaderInclusion(const NamedDecl &OriginalName) const final { 53 auto [Path, HeaderName] = getBoostHeader(OriginalName); 54 return ((IncludeSystem ? "<boost/" : "boost/") + Path + 55 (Path.empty() ? "" : "/") + HeaderName + 56 (IncludeSystem ? ".hpp>" : ".hpp")) 57 .str(); 58 } 59 60 private: 61 SmallVector<UseRangesCheck::Signature> Signatures; 62 bool IncludeSystem; 63 }; 64 65 /// Creates replaces where the header file lives in 66 /// `boost/algorithm/<FUNC_NAME>.hpp` and the function is named 67 /// `boost::range::<FUNC_NAME>` 68 class BoostRangeAlgorithmReplacer : public BoostReplacer { 69 public: 70 using BoostReplacer::BoostReplacer; 71 72 std::pair<StringRef, StringRef> 73 getBoostName(const NamedDecl &OriginalName) const override { 74 return {"range", OriginalName.getName()}; 75 } 76 77 std::pair<StringRef, StringRef> 78 getBoostHeader(const NamedDecl &OriginalName) const override { 79 return {"range/algorithm", OriginalName.getName()}; 80 } 81 }; 82 83 /// Creates replaces where the header file lives in 84 /// `boost/algorithm/<CUSTOM_HEADER>.hpp` and the function is named 85 /// `boost::range::<FUNC_NAME>` 86 class CustomBoostAlgorithmHeaderReplacer : public BoostRangeAlgorithmReplacer { 87 public: 88 CustomBoostAlgorithmHeaderReplacer( 89 StringRef HeaderName, ArrayRef<UseRangesCheck::Signature> Signatures, 90 bool IncludeSystem) 91 : BoostRangeAlgorithmReplacer(Signatures, IncludeSystem), 92 HeaderName(HeaderName) {} 93 94 std::pair<StringRef, StringRef> 95 getBoostHeader(const NamedDecl & /*OriginalName*/) const override { 96 return {"range/algorithm", HeaderName}; 97 } 98 99 private: 100 StringRef HeaderName; 101 }; 102 103 /// Creates replaces where the header file lives in 104 /// `boost/algorithm/<SUB_HEADER>.hpp` and the function is named 105 /// `boost::algorithm::<FUNC_NAME>` 106 class BoostAlgorithmReplacer : public BoostReplacer { 107 public: 108 BoostAlgorithmReplacer(StringRef SubHeader, 109 ArrayRef<UseRangesCheck::Signature> Signatures, 110 bool IncludeSystem) 111 : BoostReplacer(Signatures, IncludeSystem), 112 SubHeader(("algorithm/" + SubHeader).str()) {} 113 std::pair<StringRef, StringRef> 114 getBoostName(const NamedDecl &OriginalName) const override { 115 return {"algorithm", OriginalName.getName()}; 116 } 117 118 std::pair<StringRef, StringRef> 119 getBoostHeader(const NamedDecl &OriginalName) const override { 120 return {SubHeader, OriginalName.getName()}; 121 } 122 123 private: 124 std::string SubHeader; 125 }; 126 127 /// Creates replaces where the header file lives in 128 /// `boost/algorithm/<SUB_HEADER>/<HEADER_NAME>.hpp` and the function is named 129 /// `boost::algorithm::<FUNC_NAME>` 130 class CustomBoostAlgorithmReplacer : public BoostReplacer { 131 public: 132 CustomBoostAlgorithmReplacer(StringRef SubHeader, StringRef HeaderName, 133 ArrayRef<UseRangesCheck::Signature> Signatures, 134 bool IncludeSystem) 135 : BoostReplacer(Signatures, IncludeSystem), 136 SubHeader(("algorithm/" + SubHeader).str()), HeaderName(HeaderName) {} 137 std::pair<StringRef, StringRef> 138 getBoostName(const NamedDecl &OriginalName) const override { 139 return {"algorithm", OriginalName.getName()}; 140 } 141 142 std::pair<StringRef, StringRef> 143 getBoostHeader(const NamedDecl & /*OriginalName*/) const override { 144 return {SubHeader, HeaderName}; 145 } 146 147 private: 148 std::string SubHeader; 149 StringRef HeaderName; 150 }; 151 152 /// A Replacer that is used for functions that just call a new overload 153 class MakeOverloadReplacer : public UseRangesCheck::Replacer { 154 public: 155 explicit MakeOverloadReplacer(ArrayRef<UseRangesCheck::Signature> Signatures) 156 : Signatures(Signatures) {} 157 158 ArrayRef<UseRangesCheck::Signature> 159 getReplacementSignatures() const override { 160 return Signatures; 161 } 162 163 std::optional<std::string> 164 getReplaceName(const NamedDecl & /* OriginalName */) const override { 165 return std::nullopt; 166 } 167 168 std::optional<std::string> 169 getHeaderInclusion(const NamedDecl & /* OriginalName */) const override { 170 return std::nullopt; 171 } 172 173 private: 174 SmallVector<UseRangesCheck::Signature> Signatures; 175 }; 176 177 /// A replacer that replaces functions with an equivalent named function in the 178 /// root boost namespace 179 class FixedBoostReplace : public BoostReplacer { 180 public: 181 FixedBoostReplace(StringRef Header, 182 ArrayRef<UseRangesCheck::Signature> Signatures, 183 bool IncludeBoostSystem) 184 : BoostReplacer(Signatures, IncludeBoostSystem), Header(Header) {} 185 186 std::pair<StringRef, StringRef> 187 getBoostName(const NamedDecl &OriginalName) const override { 188 return {{}, OriginalName.getName()}; 189 } 190 191 std::pair<StringRef, StringRef> 192 getBoostHeader(const NamedDecl & /* OriginalName */) const override { 193 return {{}, Header}; 194 } 195 196 private: 197 StringRef Header; 198 }; 199 200 } // namespace 201 202 utils::UseRangesCheck::ReplacerMap UseRangesCheck::getReplacerMap() const { 203 204 ReplacerMap Results; 205 static const Signature SingleSig = {{0}}; 206 static const Signature TwoSig = {{0}, {2}}; 207 const auto AddFrom = 208 [&Results](llvm::IntrusiveRefCntPtr<UseRangesCheck::Replacer> Replacer, 209 std::initializer_list<StringRef> Names, StringRef Prefix) { 210 llvm::SmallString<64> Buffer; 211 for (const auto &Name : Names) { 212 Buffer.assign({"::", Prefix, (Prefix.empty() ? "" : "::"), Name}); 213 Results.try_emplace(Buffer, Replacer); 214 } 215 }; 216 217 const auto AddFromStd = 218 [&](llvm::IntrusiveRefCntPtr<UseRangesCheck::Replacer> Replacer, 219 std::initializer_list<StringRef> Names) { 220 AddFrom(Replacer, Names, "std"); 221 }; 222 223 const auto AddFromBoost = 224 [&](llvm::IntrusiveRefCntPtr<UseRangesCheck::Replacer> Replacer, 225 std::initializer_list< 226 std::pair<StringRef, std::initializer_list<StringRef>>> 227 NamespaceAndNames) { 228 for (auto [Namespace, Names] : NamespaceAndNames) 229 AddFrom(Replacer, Names, 230 SmallString<64>{"boost", (Namespace.empty() ? "" : "::"), 231 Namespace}); 232 }; 233 234 AddFromStd(llvm::makeIntrusiveRefCnt<CustomBoostAlgorithmHeaderReplacer>( 235 "set_algorithm", TwoSig, IncludeBoostSystem), 236 {"includes", "set_union", "set_intersection", "set_difference", 237 "set_symmetric_difference"}); 238 239 AddFromStd(llvm::makeIntrusiveRefCnt<BoostRangeAlgorithmReplacer>( 240 SingleSig, IncludeBoostSystem), 241 {"unique", "lower_bound", "stable_sort", 242 "equal_range", "remove_if", "sort", 243 "random_shuffle", "remove_copy", "stable_partition", 244 "remove_copy_if", "count", "copy_backward", 245 "reverse_copy", "adjacent_find", "remove", 246 "upper_bound", "binary_search", "replace_copy_if", 247 "for_each", "generate", "count_if", 248 "min_element", "reverse", "replace_copy", 249 "fill", "unique_copy", "transform", 250 "copy", "replace", "find", 251 "replace_if", "find_if", "partition", 252 "max_element"}); 253 254 AddFromStd(llvm::makeIntrusiveRefCnt<BoostRangeAlgorithmReplacer>( 255 TwoSig, IncludeBoostSystem), 256 {"find_end", "merge", "partial_sort_copy", "find_first_of", 257 "search", "lexicographical_compare", "equal", "mismatch"}); 258 259 AddFromStd(llvm::makeIntrusiveRefCnt<CustomBoostAlgorithmHeaderReplacer>( 260 "permutation", SingleSig, IncludeBoostSystem), 261 {"next_permutation", "prev_permutation"}); 262 263 AddFromStd(llvm::makeIntrusiveRefCnt<CustomBoostAlgorithmHeaderReplacer>( 264 "heap_algorithm", SingleSig, IncludeBoostSystem), 265 {"push_heap", "pop_heap", "make_heap", "sort_heap"}); 266 267 AddFromStd(llvm::makeIntrusiveRefCnt<BoostAlgorithmReplacer>( 268 "cxx11", SingleSig, IncludeBoostSystem), 269 {"copy_if", "is_permutation", "is_partitioned", "find_if_not", 270 "partition_copy", "any_of", "iota", "all_of", "partition_point", 271 "is_sorted", "none_of"}); 272 273 AddFromStd(llvm::makeIntrusiveRefCnt<CustomBoostAlgorithmReplacer>( 274 "cxx11", "is_sorted", SingleSig, IncludeBoostSystem), 275 {"is_sorted_until"}); 276 277 AddFromStd(llvm::makeIntrusiveRefCnt<FixedBoostReplace>( 278 "range/numeric", SingleSig, IncludeBoostSystem), 279 {"accumulate", "partial_sum", "adjacent_difference"}); 280 281 if (getLangOpts().CPlusPlus17) 282 AddFromStd(llvm::makeIntrusiveRefCnt<BoostAlgorithmReplacer>( 283 "cxx17", SingleSig, IncludeBoostSystem), 284 {"reduce"}); 285 286 AddFromBoost(llvm::makeIntrusiveRefCnt<MakeOverloadReplacer>(SingleSig), 287 {{"algorithm", 288 {"reduce", 289 "find_backward", 290 "find_not_backward", 291 "find_if_backward", 292 "find_if_not_backward", 293 "hex", 294 "hex_lower", 295 "unhex", 296 "is_partitioned_until", 297 "is_palindrome", 298 "copy_if", 299 "copy_while", 300 "copy_until", 301 "copy_if_while", 302 "copy_if_until", 303 "is_permutation", 304 "is_partitioned", 305 "one_of", 306 "one_of_equal", 307 "find_if_not", 308 "partition_copy", 309 "any_of", 310 "any_of_equal", 311 "iota", 312 "all_of", 313 "all_of_equal", 314 "partition_point", 315 "is_sorted_until", 316 "is_sorted", 317 "is_increasing", 318 "is_decreasing", 319 "is_strictly_increasing", 320 "is_strictly_decreasing", 321 "none_of", 322 "none_of_equal", 323 "clamp_range"}}}); 324 325 AddFromBoost( 326 llvm::makeIntrusiveRefCnt<MakeOverloadReplacer>(TwoSig), 327 {{"algorithm", {"apply_permutation", "apply_reverse_permutation"}}}); 328 329 return Results; 330 } 331 332 UseRangesCheck::UseRangesCheck(StringRef Name, ClangTidyContext *Context) 333 : utils::UseRangesCheck(Name, Context), 334 IncludeBoostSystem(Options.get("IncludeBoostSystem", true)), 335 UseReversePipe(Options.get("UseReversePipe", false)) {} 336 337 void UseRangesCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) { 338 utils::UseRangesCheck::storeOptions(Opts); 339 Options.store(Opts, "IncludeBoostSystem", IncludeBoostSystem); 340 Options.store(Opts, "UseReversePipe", UseReversePipe); 341 } 342 343 DiagnosticBuilder UseRangesCheck::createDiag(const CallExpr &Call) { 344 DiagnosticBuilder D = 345 diag(Call.getBeginLoc(), "use a %0 version of this algorithm"); 346 D << (Call.getDirectCallee()->isInStdNamespace() ? "boost" : "ranged"); 347 return D; 348 } 349 ArrayRef<std::pair<StringRef, StringRef>> 350 UseRangesCheck::getFreeBeginEndMethods() const { 351 static const std::pair<StringRef, StringRef> Refs[] = { 352 {"::std::begin", "::std::end"}, 353 {"::std::cbegin", "::std::cend"}, 354 {"::boost::range_adl_barrier::begin", "::boost::range_adl_barrier::end"}, 355 {"::boost::range_adl_barrier::const_begin", 356 "::boost::range_adl_barrier::const_end"}, 357 }; 358 return Refs; 359 } 360 std::optional<UseRangesCheck::ReverseIteratorDescriptor> 361 UseRangesCheck::getReverseDescriptor() const { 362 static const std::pair<StringRef, StringRef> Refs[] = { 363 {"::std::rbegin", "::std::rend"}, 364 {"::std::crbegin", "::std::crend"}, 365 {"::boost::rbegin", "::boost::rend"}, 366 {"::boost::const_rbegin", "::boost::const_rend"}, 367 }; 368 return ReverseIteratorDescriptor{ 369 UseReversePipe ? "boost::adaptors::reversed" : "boost::adaptors::reverse", 370 IncludeBoostSystem ? "<boost/range/adaptor/reversed.hpp>" 371 : "boost/range/adaptor/reversed.hpp", 372 Refs, UseReversePipe}; 373 } 374 } // namespace clang::tidy::boost 375