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