mplement __has_unique_object_representations

A helper builtin to facilitate implementing the
std::has_unique_object_representations type trait.

Requested here: https://bugs.llvm.org/show_bug.cgi?id=34942
Also already exists in GCC and MSVC.

Differential Revision: https://reviews.llvm.org/D39064


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@316518 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 150 insertions, 0 deletions

diff --git a/lib/AST/Type.cpp b/lib/AST/Type.cpp
index cc5a00b584..15af195064 100644
--- a/lib/AST/Type.cpp
+++ b/lib/AST/Type.cpp
@@ -2166,6 +2166,152 @@ bool QualType::isTriviallyCopyableType(const ASTContext &Context) const {
   return false;
 }
 
+bool QualType::unionHasUniqueObjectRepresentations(
+    const ASTContext &Context) const {
+  assert((*this)->isUnionType() && "must be union type");
+  CharUnits UnionSize = Context.getTypeSizeInChars(*this);
+  const RecordDecl *Union = getTypePtr()->getAs<RecordType>()->getDecl();
+
+  for (const auto *Field : Union->fields()) {
+    if (!Field->getType().hasUniqueObjectRepresentations(Context))
+      return false;
+    CharUnits FieldSize = Context.getTypeSizeInChars(Field->getType());
+    if (FieldSize != UnionSize)
+      return false;
+  }
+  return true;
+}
+
+bool isStructEmpty(QualType Ty) {
+  assert(Ty.getTypePtr()->isStructureOrClassType() &&
+         "Must be struct or class");
+  const RecordDecl *RD = Ty.getTypePtr()->getAs<RecordType>()->getDecl();
+
+  if (!RD->field_empty())
+    return false;
+
+  if (const CXXRecordDecl *ClassDecl = dyn_cast<CXXRecordDecl>(RD)) {
+    return ClassDecl->isEmpty();
+  }
+
+  return true;
+}
+
+bool QualType::structHasUniqueObjectRepresentations(
+    const ASTContext &Context) const {
+  assert((*this)->isStructureOrClassType() && "Must be struct or class");
+  const RecordDecl *RD = getTypePtr()->getAs<RecordType>()->getDecl();
+
+  if (isStructEmpty(*this))
+    return false;
+
+  // Check base types.
+  CharUnits BaseSize{};
+  if (const CXXRecordDecl *ClassDecl = dyn_cast<CXXRecordDecl>(RD)) {
+    for (const auto Base : ClassDecl->bases()) {
+      if (Base.isVirtual())
+        return false;
+
+      // Empty bases are permitted, otherwise ensure base has unique
+      // representation. Also, Empty Base Optimization means that an
+      // Empty base takes up 0 size.
+      if (!isStructEmpty(Base.getType())) {
+        if (!Base.getType().structHasUniqueObjectRepresentations(Context))
+          return false;
+        BaseSize += Context.getTypeSizeInChars(Base.getType());
+      }
+    }
+  }
+
+  CharUnits StructSize = Context.getTypeSizeInChars(*this);
+
+  // This struct obviously has bases that keep it from being 'empty', so
+  // checking fields is no longer required.  Ensure that the struct size
+  // is the sum of the bases.
+  if (RD->field_empty())
+    return StructSize == BaseSize;
+  ;
+
+  CharUnits CurOffset =
+      Context.toCharUnitsFromBits(Context.getFieldOffset(*RD->field_begin()));
+
+  // If the first field isn't at the sum of the size of the bases, there
+  // is padding somewhere.
+  if (BaseSize != CurOffset)
+    return false;
+
+  for (const auto *Field : RD->fields()) {
+    if (!Field->getType().hasUniqueObjectRepresentations(Context))
+      return false;
+    CharUnits FieldSize = Context.getTypeSizeInChars(Field->getType());
+    CharUnits FieldOffset =
+        Context.toCharUnitsFromBits(Context.getFieldOffset(Field));
+    // Has padding between fields.
+    if (FieldOffset != CurOffset)
+      return false;
+    CurOffset += FieldSize;
+  }
+  // Check for tail padding.
+  return CurOffset == StructSize;
+}
+
+bool QualType::hasUniqueObjectRepresentations(const ASTContext &Context) const {
+  // C++17 [meta.unary.prop]:
+  //   The predicate condition for a template specialization
+  //   has_unique_object_representations<T> shall be
+  //   satisfied if and only if:
+  //     (9.1) — T is trivially copyable, and
+  //     (9.2) — any two objects of type T with the same value have the same
+  //     object representation, where two objects
+  //   of array or non-union class type are considered to have the same value
+  //   if their respective sequences of
+  //   direct subobjects have the same values, and two objects of union type
+  //   are considered to have the same
+  //   value if they have the same active member and the corresponding members
+  //   have the same value.
+  //   The set of scalar types for which this condition holds is
+  //   implementation-defined. [ Note: If a type has padding
+  //   bits, the condition does not hold; otherwise, the condition holds true
+  //   for unsigned integral types. — end
+  //   note ]
+  if (isNull())
+    return false;
+
+  // Arrays are unique only if their element type is unique.
+  if ((*this)->isArrayType())
+    return Context.getBaseElementType(*this).hasUniqueObjectRepresentations(
+        Context);
+
+  // (9.1) — T is trivially copyable, and
+  if (!isTriviallyCopyableType(Context))
+    return false;
+
+  // Functions are not unique.
+  if ((*this)->isFunctionType())
+    return false;
+
+  // All integrals and enums are unique!
+  if ((*this)->isIntegralOrEnumerationType())
+    return true;
+
+  // All pointers are unique, since they're just integrals.
+  if ((*this)->isPointerType() || (*this)->isMemberPointerType())
+    return true;
+
+  if ((*this)->isRecordType()) {
+    const RecordDecl *Record = getTypePtr()->getAs<RecordType>()->getDecl();
+
+    // Lambda types are not unique, so exclude them immediately.
+    if (Record->isLambda())
+      return false;
+
+    if (Record->isUnion())
+      return unionHasUniqueObjectRepresentations(Context);
+    return structHasUniqueObjectRepresentations(Context);
+  }
+  return false;
+}
+
 bool QualType::isNonWeakInMRRWithObjCWeak(const ASTContext &Context) const {
   return !Context.getLangOpts().ObjCAutoRefCount &&
          Context.getLangOpts().ObjCWeak &&
diff --git a/lib/Parse/ParseExpr.cpp b/lib/Parse/ParseExpr.cpp
index 5e0688ca58..bff6d9cc19 100644
--- a/lib/Parse/ParseExpr.cpp
+++ b/lib/Parse/ParseExpr.cpp
@@ -716,6 +716,7 @@ class CastExpressionIdValidator : public CorrectionCandidateCallback {
 ///                   '__is_sealed'                           [MS]
 ///                   '__is_trivial'
 ///                   '__is_union'
+///                   '__has_unique_object_representations'
 ///
 /// [Clang] unary-type-trait:
 ///                   '__is_aggregate'
diff --git a/lib/Sema/SemaExprCXX.cpp b/lib/Sema/SemaExprCXX.cpp
index 7f5b792e8c..1ed714f8c8 100644
--- a/lib/Sema/SemaExprCXX.cpp
+++ b/lib/Sema/SemaExprCXX.cpp
@@ -4175,6 +4175,7 @@ static bool CheckUnaryTypeTraitTypeCompleteness(Sema &S, TypeTrait UTT,
   case UTT_IsDestructible:
   case UTT_IsNothrowDestructible:
   case UTT_IsTriviallyDestructible:
+  case UTT_HasUniqueObjectRepresentations:
     if (ArgTy->isIncompleteArrayType() || ArgTy->isVoidType())
       return true;
 
@@ -4614,6 +4615,8 @@ static bool EvaluateUnaryTypeTrait(Sema &Self, TypeTrait UTT,
     //   Returns True if and only if T is a complete type at the point of the
     //   function call.
     return !T->isIncompleteType();
+  case UTT_HasUniqueObjectRepresentations:
+    return T.hasUniqueObjectRepresentations(C);
   }
 }