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
21using namespace clang;
22
23Optional<ComparisonCategoryType>
24clang::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
43bool 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 retreiving 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.
66llvm::APSInt ComparisonCategoryInfo::ValueInfo::getIntValue() const {
67  assert(hasValidIntValue() && "must have a valid value");
68  return VD->evaluateValue()->getStructField(0).getInt();
69}
70
71ComparisonCategoryInfo::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
89static 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
100static 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
111const ComparisonCategoryInfo *
112ComparisonCategories::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
124const ComparisonCategoryInfo *
125ComparisonCategories::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
160const 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
166QualType ComparisonCategoryInfo::getType() const {
167  assert(Record);
168  return QualType(Record->getTypeForDecl(), 0);
169}
170
171StringRef 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
184StringRef 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
201std::vector<ComparisonCategoryResult>
202ComparisonCategories::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