1 //===- ComparisonCategories.cpp - 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 #include "clang/AST/ComparisonCategories.h"
15 #include "clang/AST/ASTContext.h"
16 #include "clang/AST/Decl.h"
17 #include "clang/AST/DeclCXX.h"
18 #include "clang/AST/Type.h"
19 #include "llvm/ADT/SmallVector.h"
20 
21 using namespace clang;
22 
23 Optional<ComparisonCategoryType>
24 clang::getComparisonCategoryForBuiltinCmp(QualType T) {
25   using CCT = ComparisonCategoryType;
26 
27   if (T->isIntegralOrEnumerationType())
28     return CCT::StrongOrdering;
29 
30   if (T->isRealFloatingType())
31     return CCT::PartialOrdering;
32 
33   // C++2a [expr.spaceship]p8: If the composite pointer type is an object
34   // pointer type, p <=> q is of type std::strong_ordering.
35   // Note: this assumes neither operand is a null pointer constant.
36   if (T->isObjectPointerType())
37     return CCT::StrongOrdering;
38 
39   // TODO: Extend support for operator<=> to ObjC types.
40   return llvm::None;
41 }
42 
43 bool ComparisonCategoryInfo::ValueInfo::hasValidIntValue() const {
44   assert(VD && "must have var decl");
45   if (!VD->isUsableInConstantExpressions(VD->getASTContext()))
46     return false;
47 
48   // Before we attempt to get the value of the first field, ensure that we
49   // actually have one (and only one) field.
50   auto *Record = VD->getType()->getAsCXXRecordDecl();
51   if (std::distance(Record->field_begin(), Record->field_end()) != 1 ||
52       !Record->field_begin()->getType()->isIntegralOrEnumerationType())
53     return false;
54 
55   return true;
56 }
57 
58 /// Attempt to determine the integer value used to represent the comparison
59 /// category result by evaluating the initializer for the specified VarDecl as
60 /// a constant expression and retrieving the value of the class's first
61 /// (and only) field.
62 ///
63 /// Note: The STL types are expected to have the form:
64 ///    struct X { T value; };
65 /// where T is an integral or enumeration type.
66 llvm::APSInt ComparisonCategoryInfo::ValueInfo::getIntValue() const {
67   assert(hasValidIntValue() && "must have a valid value");
68   return VD->evaluateValue()->getStructField(0).getInt();
69 }
70 
71 ComparisonCategoryInfo::ValueInfo *ComparisonCategoryInfo::lookupValueInfo(
72     ComparisonCategoryResult ValueKind) const {
73   // Check if we already have a cache entry for this value.
74   auto It = llvm::find_if(
75       Objects, [&](ValueInfo const &Info) { return Info.Kind == ValueKind; });
76   if (It != Objects.end())
77     return &(*It);
78 
79   // We don't have a cached result. Lookup the variable declaration and create
80   // a new entry representing it.
81   DeclContextLookupResult Lookup = Record->getCanonicalDecl()->lookup(
82       &Ctx.Idents.get(ComparisonCategories::getResultString(ValueKind)));
83   if (Lookup.empty() || !isa<VarDecl>(Lookup.front()))
84     return nullptr;
85   Objects.emplace_back(ValueKind, cast<VarDecl>(Lookup.front()));
86   return &Objects.back();
87 }
88 
89 static const NamespaceDecl *lookupStdNamespace(const ASTContext &Ctx,
90                                                NamespaceDecl *&StdNS) {
91   if (!StdNS) {
92     DeclContextLookupResult Lookup =
93         Ctx.getTranslationUnitDecl()->lookup(&Ctx.Idents.get("std"));
94     if (!Lookup.empty())
95       StdNS = dyn_cast<NamespaceDecl>(Lookup.front());
96   }
97   return StdNS;
98 }
99 
100 static CXXRecordDecl *lookupCXXRecordDecl(const ASTContext &Ctx,
101                                           const NamespaceDecl *StdNS,
102                                           ComparisonCategoryType Kind) {
103   StringRef Name = ComparisonCategories::getCategoryString(Kind);
104   DeclContextLookupResult Lookup = StdNS->lookup(&Ctx.Idents.get(Name));
105   if (!Lookup.empty())
106     if (CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(Lookup.front()))
107       return RD;
108   return nullptr;
109 }
110 
111 const ComparisonCategoryInfo *
112 ComparisonCategories::lookupInfo(ComparisonCategoryType Kind) const {
113   auto It = Data.find(static_cast<char>(Kind));
114   if (It != Data.end())
115     return &It->second;
116 
117   if (const NamespaceDecl *NS = lookupStdNamespace(Ctx, StdNS))
118     if (CXXRecordDecl *RD = lookupCXXRecordDecl(Ctx, NS, Kind))
119       return &Data.try_emplace((char)Kind, Ctx, RD, Kind).first->second;
120 
121   return nullptr;
122 }
123 
124 const ComparisonCategoryInfo *
125 ComparisonCategories::lookupInfoForType(QualType Ty) const {
126   assert(!Ty.isNull() && "type must be non-null");
127   using CCT = ComparisonCategoryType;
128   auto *RD = Ty->getAsCXXRecordDecl();
129   if (!RD)
130     return nullptr;
131 
132   // Check to see if we have information for the specified type cached.
133   const auto *CanonRD = RD->getCanonicalDecl();
134   for (auto &KV : Data) {
135     const ComparisonCategoryInfo &Info = KV.second;
136     if (CanonRD == Info.Record->getCanonicalDecl())
137       return &Info;
138   }
139 
140   if (!RD->getEnclosingNamespaceContext()->isStdNamespace())
141     return nullptr;
142 
143   // If not, check to see if the decl names a type in namespace std with a name
144   // matching one of the comparison category types.
145   for (unsigned I = static_cast<unsigned>(CCT::First),
146                 End = static_cast<unsigned>(CCT::Last);
147        I <= End; ++I) {
148     CCT Kind = static_cast<CCT>(I);
149 
150     // We've found the comparison category type. Build a new cache entry for
151     // it.
152     if (getCategoryString(Kind) == RD->getName())
153       return &Data.try_emplace((char)Kind, Ctx, RD, Kind).first->second;
154   }
155 
156   // We've found nothing. This isn't a comparison category type.
157   return nullptr;
158 }
159 
160 const ComparisonCategoryInfo &ComparisonCategories::getInfoForType(QualType Ty) const {
161   const ComparisonCategoryInfo *Info = lookupInfoForType(Ty);
162   assert(Info && "info for comparison category not found");
163   return *Info;
164 }
165 
166 QualType ComparisonCategoryInfo::getType() const {
167   assert(Record);
168   return QualType(Record->getTypeForDecl(), 0);
169 }
170 
171 StringRef ComparisonCategories::getCategoryString(ComparisonCategoryType Kind) {
172   using CCKT = ComparisonCategoryType;
173   switch (Kind) {
174   case CCKT::PartialOrdering:
175     return "partial_ordering";
176   case CCKT::WeakOrdering:
177     return "weak_ordering";
178   case CCKT::StrongOrdering:
179     return "strong_ordering";
180   }
181   llvm_unreachable("unhandled cases in switch");
182 }
183 
184 StringRef ComparisonCategories::getResultString(ComparisonCategoryResult Kind) {
185   using CCVT = ComparisonCategoryResult;
186   switch (Kind) {
187   case CCVT::Equal:
188     return "equal";
189   case CCVT::Equivalent:
190     return "equivalent";
191   case CCVT::Less:
192     return "less";
193   case CCVT::Greater:
194     return "greater";
195   case CCVT::Unordered:
196     return "unordered";
197   }
198   llvm_unreachable("unhandled case in switch");
199 }
200 
201 std::vector<ComparisonCategoryResult>
202 ComparisonCategories::getPossibleResultsForType(ComparisonCategoryType Type) {
203   using CCT = ComparisonCategoryType;
204   using CCR = ComparisonCategoryResult;
205   std::vector<CCR> Values;
206   Values.reserve(4);
207   bool IsStrong = Type == CCT::StrongOrdering;
208   Values.push_back(IsStrong ? CCR::Equal : CCR::Equivalent);
209   Values.push_back(CCR::Less);
210   Values.push_back(CCR::Greater);
211   if (Type == CCT::PartialOrdering)
212     Values.push_back(CCR::Unordered);
213   return Values;
214 }
215