1 //===- ComparisonCategories.h - Three Way Comparison Data -------*- C++ -*-===// 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 // This file defines the Comparison Category enum and data types, which 10 // store the types and expressions needed to support operator<=> 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CLANG_AST_COMPARISONCATEGORIES_H 15 #define LLVM_CLANG_AST_COMPARISONCATEGORIES_H 16 17 #include "clang/Basic/LLVM.h" 18 #include "llvm/ADT/APSInt.h" 19 #include "llvm/ADT/DenseMap.h" 20 #include <array> 21 #include <cassert> 22 #include <optional> 23 #include <vector> 24 25 namespace llvm { 26 class StringRef; 27 class APSInt; 28 } 29 30 namespace clang { 31 32 class ASTContext; 33 class VarDecl; 34 class CXXRecordDecl; 35 class Sema; 36 class QualType; 37 class NamespaceDecl; 38 39 /// An enumeration representing the different comparison categories 40 /// types. 41 /// 42 /// C++20 [cmp.categories.pre] The types partial_ordering, weak_ordering, and 43 /// strong_ordering are collectively termed the comparison category types. 44 enum class ComparisonCategoryType : unsigned char { 45 PartialOrdering, 46 WeakOrdering, 47 StrongOrdering, 48 First = PartialOrdering, 49 Last = StrongOrdering 50 }; 51 52 /// Determine the common comparison type, as defined in C++2a 53 /// [class.spaceship]p4. 54 inline ComparisonCategoryType commonComparisonType(ComparisonCategoryType A, 55 ComparisonCategoryType B) { 56 return A < B ? A : B; 57 } 58 59 /// Get the comparison category that should be used when comparing values of 60 /// type \c T. 61 std::optional<ComparisonCategoryType> 62 getComparisonCategoryForBuiltinCmp(QualType T); 63 64 /// An enumeration representing the possible results of a three-way 65 /// comparison. These values map onto instances of comparison category types 66 /// defined in the standard library. e.g. 'std::strong_ordering::less'. 67 enum class ComparisonCategoryResult : unsigned char { 68 Equal, 69 Equivalent, 70 Less, 71 Greater, 72 Unordered, 73 Last = Unordered 74 }; 75 76 class ComparisonCategoryInfo { 77 friend class ComparisonCategories; 78 friend class Sema; 79 80 public: 81 ComparisonCategoryInfo(const ASTContext &Ctx, CXXRecordDecl *RD, 82 ComparisonCategoryType Kind) 83 : Ctx(Ctx), Record(RD), Kind(Kind) {} 84 85 struct ValueInfo { 86 ComparisonCategoryResult Kind; 87 VarDecl *VD; 88 89 ValueInfo(ComparisonCategoryResult Kind, VarDecl *VD) 90 : Kind(Kind), VD(VD) {} 91 92 /// True iff we've successfully evaluated the variable as a constant 93 /// expression and extracted its integer value. 94 bool hasValidIntValue() const; 95 96 /// Get the constant integer value used by this variable to represent 97 /// the comparison category result type. 98 llvm::APSInt getIntValue() const; 99 }; 100 private: 101 const ASTContext &Ctx; 102 103 /// A map containing the comparison category result decls from the 104 /// standard library. The key is a value of ComparisonCategoryResult. 105 mutable llvm::SmallVector< 106 ValueInfo, static_cast<unsigned>(ComparisonCategoryResult::Last) + 1> 107 Objects; 108 109 /// Lookup the ValueInfo struct for the specified ValueKind. If the 110 /// VarDecl for the value cannot be found, nullptr is returned. 111 /// 112 /// If the ValueInfo does not have a valid integer value the variable 113 /// is evaluated as a constant expression to determine that value. 114 ValueInfo *lookupValueInfo(ComparisonCategoryResult ValueKind) const; 115 116 public: 117 /// The declaration for the comparison category type from the 118 /// standard library. 119 const CXXRecordDecl *Record = nullptr; 120 121 /// The Kind of the comparison category type 122 ComparisonCategoryType Kind; 123 124 public: 125 QualType getType() const; 126 127 const ValueInfo *getValueInfo(ComparisonCategoryResult ValueKind) const { 128 ValueInfo *Info = lookupValueInfo(ValueKind); 129 assert(Info && 130 "comparison category does not contain the specified result kind"); 131 assert(Info->hasValidIntValue() && 132 "couldn't determine the integer constant for this value"); 133 return Info; 134 } 135 136 /// True iff the comparison is "strong". i.e. it checks equality and 137 /// not equivalence. 138 bool isStrong() const { 139 using CCK = ComparisonCategoryType; 140 return Kind == CCK::StrongOrdering; 141 } 142 143 /// True iff the comparison is not totally ordered. 144 bool isPartial() const { 145 using CCK = ComparisonCategoryType; 146 return Kind == CCK::PartialOrdering; 147 } 148 149 /// Converts the specified result kind into the correct result kind 150 /// for this category. Specifically it lowers strong equality results to 151 /// weak equivalence if needed. 152 ComparisonCategoryResult makeWeakResult(ComparisonCategoryResult Res) const { 153 using CCR = ComparisonCategoryResult; 154 if (!isStrong() && Res == CCR::Equal) 155 return CCR::Equivalent; 156 return Res; 157 } 158 159 const ValueInfo *getEqualOrEquiv() const { 160 return getValueInfo(makeWeakResult(ComparisonCategoryResult::Equal)); 161 } 162 const ValueInfo *getLess() const { 163 return getValueInfo(ComparisonCategoryResult::Less); 164 } 165 const ValueInfo *getGreater() const { 166 return getValueInfo(ComparisonCategoryResult::Greater); 167 } 168 const ValueInfo *getUnordered() const { 169 assert(isPartial()); 170 return getValueInfo(ComparisonCategoryResult::Unordered); 171 } 172 }; 173 174 class ComparisonCategories { 175 public: 176 static StringRef getCategoryString(ComparisonCategoryType Kind); 177 static StringRef getResultString(ComparisonCategoryResult Kind); 178 179 /// Return the list of results which are valid for the specified 180 /// comparison category type. 181 static std::vector<ComparisonCategoryResult> 182 getPossibleResultsForType(ComparisonCategoryType Type); 183 184 /// Return the comparison category information for the category 185 /// specified by 'Kind'. 186 const ComparisonCategoryInfo &getInfo(ComparisonCategoryType Kind) const { 187 const ComparisonCategoryInfo *Result = lookupInfo(Kind); 188 assert(Result != nullptr && 189 "information for specified comparison category has not been built"); 190 return *Result; 191 } 192 193 /// Return the comparison category information as specified by 194 /// `getCategoryForType(Ty)`. If the information is not already cached, 195 /// the declaration is looked up and a cache entry is created. 196 /// NOTE: Lookup is expected to succeed. Use lookupInfo if failure is 197 /// possible. 198 const ComparisonCategoryInfo &getInfoForType(QualType Ty) const; 199 200 public: 201 /// Return the cached comparison category information for the 202 /// specified 'Kind'. If no cache entry is present the comparison category 203 /// type is looked up. If lookup fails nullptr is returned. Otherwise, a 204 /// new cache entry is created and returned 205 const ComparisonCategoryInfo *lookupInfo(ComparisonCategoryType Kind) const; 206 207 ComparisonCategoryInfo *lookupInfo(ComparisonCategoryType Kind) { 208 const auto &This = *this; 209 return const_cast<ComparisonCategoryInfo *>(This.lookupInfo(Kind)); 210 } 211 212 const ComparisonCategoryInfo *lookupInfoForType(QualType Ty) const; 213 214 private: 215 friend class ASTContext; 216 217 explicit ComparisonCategories(const ASTContext &Ctx) : Ctx(Ctx) {} 218 219 const ASTContext &Ctx; 220 221 /// A map from the ComparisonCategoryType (represented as 'char') to the 222 /// cached information for the specified category. 223 mutable llvm::DenseMap<char, ComparisonCategoryInfo> Data; 224 mutable NamespaceDecl *StdNS = nullptr; 225 }; 226 227 } // namespace clang 228 229 #endif 230