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.
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:
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 
88     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   const CXXRecordDecl *Record = nullptr;
119 
120   /// The Kind of the comparison category type
121   ComparisonCategoryType Kind;
122 
123 public:
124   QualType getType() const;
125 
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.
137   bool isStrong() const {
138     using CCK = ComparisonCategoryType;
139     return Kind == CCK::StrongOrdering;
140   }
141 
142   /// True iff the comparison is not totally ordered.
143   bool isPartial() const {
144     using CCK = ComparisonCategoryType;
145     return Kind == CCK::PartialOrdering;
146   }
147 
148   /// Converts the specified result kind into the correct result kind
149   /// for this category. Specifically it lowers strong equality results to
150   /// weak equivalence if needed.
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 
158   const ValueInfo *getEqualOrEquiv() const {
159     return getValueInfo(makeWeakResult(ComparisonCategoryResult::Equal));
160   }
161   const ValueInfo *getLess() const {
162     return getValueInfo(ComparisonCategoryResult::Less);
163   }
164   const ValueInfo *getGreater() const {
165     return getValueInfo(ComparisonCategoryResult::Greater);
166   }
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'.
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 
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 
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