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 <vector>
23
24 namespace llvm {
25 class StringRef;
26 class APSInt;
27 }
28
29 namespace clang {
30
31 class ASTContext;
32 class VarDecl;
33 class CXXRecordDecl;
34 class Sema;
35 class QualType;
36 class NamespaceDecl;
37
38 /// An enumeration representing the different comparison categories
39 /// types.
40 ///
41 /// C++2a [cmp.categories.pre] The types weak_equality, strong_equality,
42 /// partial_ordering, weak_ordering, and strong_ordering are collectively
43 /// 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.
commonComparisonType(ComparisonCategoryType A,ComparisonCategoryType B)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 Optional<ComparisonCategoryType> getComparisonCategoryForBuiltinCmp(QualType T);
62
63 /// An enumeration representing the possible results of a three-way
64 /// comparison. These values map onto instances of comparison category types
65 /// defined in the standard library. e.g. 'std::strong_ordering::less'.
66 enum class ComparisonCategoryResult : unsigned char {
67 Equal,
68 Equivalent,
69 Less,
70 Greater,
71 Unordered,
72 Last = Unordered
73 };
74
75 class ComparisonCategoryInfo {
76 friend class ComparisonCategories;
77 friend class Sema;
78
79 public:
ComparisonCategoryInfo(const ASTContext & Ctx,CXXRecordDecl * RD,ComparisonCategoryType Kind)80 ComparisonCategoryInfo(const ASTContext &Ctx, CXXRecordDecl *RD,
81 ComparisonCategoryType Kind)
82 : Ctx(Ctx), Record(RD), Kind(Kind) {}
83
84 struct ValueInfo {
85 ComparisonCategoryResult Kind;
86 VarDecl *VD;
87
ValueInfoValueInfo88 ValueInfo(ComparisonCategoryResult Kind, VarDecl *VD)
89 : Kind(Kind), VD(VD) {}
90
91 /// True iff we've successfully evaluated the variable as a constant
92 /// expression and extracted its integer value.
93 bool hasValidIntValue() const;
94
95 /// Get the constant integer value used by this variable to represent
96 /// the comparison category result type.
97 llvm::APSInt getIntValue() const;
98 };
99 private:
100 const ASTContext &Ctx;
101
102 /// A map containing the comparison category result decls from the
103 /// standard library. The key is a value of ComparisonCategoryResult.
104 mutable llvm::SmallVector<
105 ValueInfo, static_cast<unsigned>(ComparisonCategoryResult::Last) + 1>
106 Objects;
107
108 /// Lookup the ValueInfo struct for the specified ValueKind. If the
109 /// VarDecl for the value cannot be found, nullptr is returned.
110 ///
111 /// If the ValueInfo does not have a valid integer value the variable
112 /// is evaluated as a constant expression to determine that value.
113 ValueInfo *lookupValueInfo(ComparisonCategoryResult ValueKind) const;
114
115 public:
116 /// The declaration for the comparison category type from the
117 /// standard library.
118 // FIXME: Make this const
119 CXXRecordDecl *Record = nullptr;
120
121 /// The Kind of the comparison category type
122 ComparisonCategoryType Kind;
123
124 public:
125 QualType getType() const;
126
getValueInfo(ComparisonCategoryResult ValueKind)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.
isStrong()138 bool isStrong() const {
139 using CCK = ComparisonCategoryType;
140 return Kind == CCK::StrongOrdering;
141 }
142
143 /// True iff the comparison is not totally ordered.
isPartial()144 bool isPartial() const {
145 using CCK = ComparisonCategoryType;
146 return Kind == CCK::PartialOrdering;
147 }
148
149 /// Converts the specified result kind into the the correct result kind
150 /// for this category. Specifically it lowers strong equality results to
151 /// weak equivalence if needed.
makeWeakResult(ComparisonCategoryResult Res)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
getEqualOrEquiv()159 const ValueInfo *getEqualOrEquiv() const {
160 return getValueInfo(makeWeakResult(ComparisonCategoryResult::Equal));
161 }
getLess()162 const ValueInfo *getLess() const {
163 return getValueInfo(ComparisonCategoryResult::Less);
164 }
getGreater()165 const ValueInfo *getGreater() const {
166 return getValueInfo(ComparisonCategoryResult::Greater);
167 }
getUnordered()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'.
getInfo(ComparisonCategoryType 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
lookupInfo(ComparisonCategoryType Kind)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
ComparisonCategories(const ASTContext & Ctx)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