lib/AST/CXXInheritance.cpp

   1 //===------ CXXInheritance.cpp - C++ Inheritance ----------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file provides routines that help analyzing C++ inheritance hierarchies.
  11 //
  12 //===----------------------------------------------------------------------===//
  13 #include "clang/AST/CXXInheritance.h"
  14 #include "clang/AST/DeclCXX.h"
  15 #include <algorithm>
  16 #include <set>
  17
  18 using namespace clang;
  19
  20 /// \brief Computes the set of declarations referenced by these base
  21 /// paths.
  22 void CXXBasePaths::ComputeDeclsFound() {
  23   assert(NumDeclsFound == 0 && !DeclsFound &&
  24          "Already computed the set of declarations");
  25
  26   std::set<NamedDecl *> Decls;
  27   for (CXXBasePaths::paths_iterator Path = begin(), PathEnd = end();
  28        Path != PathEnd; ++Path)
  29     Decls.insert(*Path->Decls.first);
  30
  31   NumDeclsFound = Decls.size();
  32   DeclsFound = new NamedDecl * [NumDeclsFound];
  33   std::copy(Decls.begin(), Decls.end(), DeclsFound);
  34 }
  35
  36 CXXBasePaths::decl_iterator CXXBasePaths::found_decls_begin() {
  37   if (NumDeclsFound == 0)
  38     ComputeDeclsFound();
  39   return DeclsFound;
  40 }
  41
  42 CXXBasePaths::decl_iterator CXXBasePaths::found_decls_end() {
  43   if (NumDeclsFound == 0)
  44     ComputeDeclsFound();
  45   return DeclsFound + NumDeclsFound;
  46 }
  47
  48 /// isAmbiguous - Determines whether the set of paths provided is
  49 /// ambiguous, i.e., there are two or more paths that refer to
  50 /// different base class subobjects of the same type. BaseType must be
  51 /// an unqualified, canonical class type.
  52 bool CXXBasePaths::isAmbiguous(QualType BaseType) {
  53   assert(BaseType.isCanonical() && "Base type must be the canonical type");
  54   assert(BaseType.hasQualifiers() == 0 && "Base type must be unqualified");
  55   std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
  56   return Subobjects.second + (Subobjects.first? 1 : 0) > 1;
  57 }
  58
  59 /// clear - Clear out all prior path information.
  60 void CXXBasePaths::clear() {
  61   Paths.clear();
  62   ClassSubobjects.clear();
  63   ScratchPath.clear();
  64   DetectedVirtual = 0;
  65 }
  66
  67 /// @brief Swaps the contents of this CXXBasePaths structure with the
  68 /// contents of Other.
  69 void CXXBasePaths::swap(CXXBasePaths &Other) {
  70   std::swap(Origin, Other.Origin);
  71   Paths.swap(Other.Paths);
  72   ClassSubobjects.swap(Other.ClassSubobjects);
  73   std::swap(FindAmbiguities, Other.FindAmbiguities);
  74   std::swap(RecordPaths, Other.RecordPaths);
  75   std::swap(DetectVirtual, Other.DetectVirtual);
  76   std::swap(DetectedVirtual, Other.DetectedVirtual);
  77 }
  78
  79 bool CXXRecordDecl::isDerivedFrom(CXXRecordDecl *Base) const {
  80   CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
  81                      /*DetectVirtual=*/false);
  82   return isDerivedFrom(Base, Paths);
  83 }
  84
  85 bool CXXRecordDecl::isDerivedFrom(CXXRecordDecl *Base, CXXBasePaths &Paths) const {
  86   if (getCanonicalDecl() == Base->getCanonicalDecl())
  87     return false;
  88
  89   Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
  90   return lookupInBases(&FindBaseClass, Base->getCanonicalDecl(), Paths);
  91 }
  92
  93 bool CXXRecordDecl::isVirtuallyDerivedFrom(CXXRecordDecl *Base) const {
  94   CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false,
  95                      /*DetectVirtual=*/false);
  96
  97   if (getCanonicalDecl() == Base->getCanonicalDecl())
  98     return false;
  99
 100   Paths.setOrigin(const_cast<CXXRecordDecl*>(this));
 101   return lookupInBases(&FindVirtualBaseClass, Base->getCanonicalDecl(), Paths);
 102 }
 103
 104 static bool BaseIsNot(const CXXRecordDecl *Base, void *OpaqueTarget) {
 105   // OpaqueTarget is a CXXRecordDecl*.
 106   return Base->getCanonicalDecl() != (const CXXRecordDecl*) OpaqueTarget;
 107 }
 108
 109 bool CXXRecordDecl::isProvablyNotDerivedFrom(const CXXRecordDecl *Base) const {
 110   return forallBases(BaseIsNot, (void*) Base->getCanonicalDecl());
 111 }
 112
 113 bool CXXRecordDecl::forallBases(ForallBasesCallback *BaseMatches,
 114                                 void *OpaqueData,
 115                                 bool AllowShortCircuit) const {
 116   llvm::SmallVector<const CXXRecordDecl*, 8> Queue;
 117
 118   const CXXRecordDecl *Record = this;
 119   bool AllMatches = true;
 120   while (true) {
 121     for (CXXRecordDecl::base_class_const_iterator
 122            I = Record->bases_begin(), E = Record->bases_end(); I != E; ++I) {
 123       const RecordType *Ty = I->getType()->getAs<RecordType>();
 124       if (!Ty) {
 125         if (AllowShortCircuit) return false;
 126         AllMatches = false;
 127         continue;
 128       }
 129
 130       CXXRecordDecl *Base =
 131             cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition());
 132       if (!Base) {
 133         if (AllowShortCircuit) return false;
 134         AllMatches = false;
 135         continue;
 136       }
 137
 138       Queue.push_back(Base);
 139       if (!BaseMatches(Base, OpaqueData)) {
 140         if (AllowShortCircuit) return false;
 141         AllMatches = false;
 142         continue;
 143       }
 144     }
 145
 146     if (Queue.empty()) break;
 147     Record = Queue.back(); // not actually a queue.
 148     Queue.pop_back();
 149   }
 150
 151   return AllMatches;
 152 }
 153
 154 bool CXXBasePaths::lookupInBases(ASTContext &Context,
 155                                  const CXXRecordDecl *Record,
 156                                CXXRecordDecl::BaseMatchesCallback *BaseMatches,
 157                                  void *UserData) {
 158   bool FoundPath = false;
 159
 160   // The access of the path down to this record.
 161   AccessSpecifier AccessToHere = ScratchPath.Access;
 162   bool IsFirstStep = ScratchPath.empty();
 163
 164   for (CXXRecordDecl::base_class_const_iterator BaseSpec = Record->bases_begin(),
 165          BaseSpecEnd = Record->bases_end();
 166        BaseSpec != BaseSpecEnd;
 167        ++BaseSpec) {
 168     // Find the record of the base class subobjects for this type.
 169     QualType BaseType = Context.getCanonicalType(BaseSpec->getType())
 170                                                           .getUnqualifiedType();
 171
 172     // C++ [temp.dep]p3:
 173     //   In the definition of a class template or a member of a class template,
 174     //   if a base class of the class template depends on a template-parameter,
 175     //   the base class scope is not examined during unqualified name lookup
 176     //   either at the point of definition of the class template or member or
 177     //   during an instantiation of the class tem- plate or member.
 178     if (BaseType->isDependentType())
 179       continue;
 180
 181     // Determine whether we need to visit this base class at all,
 182     // updating the count of subobjects appropriately.
 183     std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
 184     bool VisitBase = true;
 185     bool SetVirtual = false;
 186     if (BaseSpec->isVirtual()) {
 187       VisitBase = !Subobjects.first;
 188       Subobjects.first = true;
 189       if (isDetectingVirtual() && DetectedVirtual == 0) {
 190         // If this is the first virtual we find, remember it. If it turns out
 191         // there is no base path here, we'll reset it later.
 192         DetectedVirtual = BaseType->getAs<RecordType>();
 193         SetVirtual = true;
 194       }
 195     } else
 196       ++Subobjects.second;
 197
 198     if (isRecordingPaths()) {
 199       // Add this base specifier to the current path.
 200       CXXBasePathElement Element;
 201       Element.Base = &*BaseSpec;
 202       Element.Class = Record;
 203       if (BaseSpec->isVirtual())
 204         Element.SubobjectNumber = 0;
 205       else
 206         Element.SubobjectNumber = Subobjects.second;
 207       ScratchPath.push_back(Element);
 208
 209       // Calculate the "top-down" access to this base class.
 210       // The spec actually describes this bottom-up, but top-down is
 211       // equivalent because the definition works out as follows:
 212       // 1. Write down the access along each step in the inheritance
 213       //    chain, followed by the access of the decl itself.
 214       //    For example, in
 215       //      class A { public: int foo; };
 216       //      class B : protected A {};
 217       //      class C : public B {};
 218       //      class D : private C {};
 219       //    we would write:
 220       //      private public protected public
 221       // 2. If 'private' appears anywhere except far-left, access is denied.
 222       // 3. Otherwise, overall access is determined by the most restrictive
 223       //    access in the sequence.
 224       if (IsFirstStep)
 225         ScratchPath.Access = BaseSpec->getAccessSpecifier();
 226       else
 227         ScratchPath.Access = CXXRecordDecl::MergeAccess(AccessToHere,
 228                                                  BaseSpec->getAccessSpecifier());
 229     }
 230
 231     // Track whether there's a path involving this specific base.
 232     bool FoundPathThroughBase = false;
 233
 234     if (BaseMatches(BaseSpec, ScratchPath, UserData)) {
 235       // We've found a path that terminates at this base.
 236       FoundPath = FoundPathThroughBase = true;
 237       if (isRecordingPaths()) {
 238         // We have a path. Make a copy of it before moving on.
 239         Paths.push_back(ScratchPath);
 240       } else if (!isFindingAmbiguities()) {
 241         // We found a path and we don't care about ambiguities;
 242         // return immediately.
 243         return FoundPath;
 244       }
 245     } else if (VisitBase) {
 246       CXXRecordDecl *BaseRecord
 247         = cast<CXXRecordDecl>(BaseSpec->getType()->getAs<RecordType>()
 248                                 ->getDecl());
 249       if (lookupInBases(Context, BaseRecord, BaseMatches, UserData)) {
 250         // C++ [class.member.lookup]p2:
 251         //   A member name f in one sub-object B hides a member name f in
 252         //   a sub-object A if A is a base class sub-object of B. Any
 253         //   declarations that are so hidden are eliminated from
 254         //   consideration.
 255
 256         // There is a path to a base class that meets the criteria. If we're
 257         // not collecting paths or finding ambiguities, we're done.
 258         FoundPath = FoundPathThroughBase = true;
 259         if (!isFindingAmbiguities())
 260           return FoundPath;
 261       }
 262     }
 263
 264     // Pop this base specifier off the current path (if we're
 265     // collecting paths).
 266     if (isRecordingPaths()) {
 267       ScratchPath.pop_back();
 268     }
 269
 270     // If we set a virtual earlier, and this isn't a path, forget it again.
 271     if (SetVirtual && !FoundPathThroughBase) {
 272       DetectedVirtual = 0;
 273     }
 274   }
 275
 276   // Reset the scratch path access.
 277   ScratchPath.Access = AccessToHere;
 278
 279   return FoundPath;
 280 }
 281
 282 bool CXXRecordDecl::lookupInBases(BaseMatchesCallback *BaseMatches,
 283                                   void *UserData,
 284                                   CXXBasePaths &Paths) const {
 285   // If we didn't find anything, report that.
 286   if (!Paths.lookupInBases(getASTContext(), this, BaseMatches, UserData))
 287     return false;
 288
 289   // If we're not recording paths or we won't ever find ambiguities,
 290   // we're done.
 291   if (!Paths.isRecordingPaths() || !Paths.isFindingAmbiguities())
 292     return true;
 293
 294   // C++ [class.member.lookup]p6:
 295   //   When virtual base classes are used, a hidden declaration can be
 296   //   reached along a path through the sub-object lattice that does
 297   //   not pass through the hiding declaration. This is not an
 298   //   ambiguity. The identical use with nonvirtual base classes is an
 299   //   ambiguity; in that case there is no unique instance of the name
 300   //   that hides all the others.
 301   //
 302   // FIXME: This is an O(N^2) algorithm, but DPG doesn't see an easy
 303   // way to make it any faster.
 304   for (CXXBasePaths::paths_iterator P = Paths.begin(), PEnd = Paths.end();
 305        P != PEnd; /* increment in loop */) {
 306     bool Hidden = false;
 307
 308     for (CXXBasePath::iterator PE = P->begin(), PEEnd = P->end();
 309          PE != PEEnd && !Hidden; ++PE) {
 310       if (PE->Base->isVirtual()) {
 311         CXXRecordDecl *VBase = 0;
 312         if (const RecordType *Record = PE->Base->getType()->getAs<RecordType>())
 313           VBase = cast<CXXRecordDecl>(Record->getDecl());
 314         if (!VBase)
 315           break;
 316
 317         // The declaration(s) we found along this path were found in a
 318         // subobject of a virtual base. Check whether this virtual
 319         // base is a subobject of any other path; if so, then the
 320         // declaration in this path are hidden by that patch.
 321         for (CXXBasePaths::paths_iterator HidingP = Paths.begin(),
 322                                        HidingPEnd = Paths.end();
 323              HidingP != HidingPEnd;
 324              ++HidingP) {
 325           CXXRecordDecl *HidingClass = 0;
 326           if (const RecordType *Record
 327                        = HidingP->back().Base->getType()->getAs<RecordType>())
 328             HidingClass = cast<CXXRecordDecl>(Record->getDecl());
 329           if (!HidingClass)
 330             break;
 331
 332           if (HidingClass->isVirtuallyDerivedFrom(VBase)) {
 333             Hidden = true;
 334             break;
 335           }
 336         }
 337       }
 338     }
 339
 340     if (Hidden)
 341       P = Paths.Paths.erase(P);
 342     else
 343       ++P;
 344   }
 345
 346   return true;
 347 }
 348
 349 bool CXXRecordDecl::FindBaseClass(const CXXBaseSpecifier *Specifier,
 350                                   CXXBasePath &Path,
 351                                   void *BaseRecord) {
 352   assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord &&
 353          "User data for FindBaseClass is not canonical!");
 354   return Specifier->getType()->getAs<RecordType>()->getDecl()
 355            ->getCanonicalDecl() == BaseRecord;
 356 }
 357
 358 bool CXXRecordDecl::FindVirtualBaseClass(const CXXBaseSpecifier *Specifier,
 359                                          CXXBasePath &Path,
 360                                          void *BaseRecord) {
 361   assert(((Decl *)BaseRecord)->getCanonicalDecl() == BaseRecord &&
 362          "User data for FindBaseClass is not canonical!");
 363   return Specifier->isVirtual() &&
 364          Specifier->getType()->getAs<RecordType>()->getDecl()
 365            ->getCanonicalDecl() == BaseRecord;
 366 }
 367
 368 bool CXXRecordDecl::FindTagMember(const CXXBaseSpecifier *Specifier,
 369                                   CXXBasePath &Path,
 370                                   void *Name) {
 371   RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
 372
 373   DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
 374   for (Path.Decls = BaseRecord->lookup(N);
 375        Path.Decls.first != Path.Decls.second;
 376        ++Path.Decls.first) {
 377     if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag))
 378       return true;
 379   }
 380
 381   return false;
 382 }
 383
 384 bool CXXRecordDecl::FindOrdinaryMember(const CXXBaseSpecifier *Specifier,
 385                                        CXXBasePath &Path,
 386                                        void *Name) {
 387   RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
 388
 389   const unsigned IDNS = IDNS_Ordinary | IDNS_Tag | IDNS_Member;
 390   DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
 391   for (Path.Decls = BaseRecord->lookup(N);
 392        Path.Decls.first != Path.Decls.second;
 393        ++Path.Decls.first) {
 394     if ((*Path.Decls.first)->isInIdentifierNamespace(IDNS))
 395       return true;
 396   }
 397
 398   return false;
 399 }
 400
 401 bool CXXRecordDecl::
 402 FindNestedNameSpecifierMember(const CXXBaseSpecifier *Specifier,
 403                               CXXBasePath &Path,
 404                               void *Name) {
 405   RecordDecl *BaseRecord = Specifier->getType()->getAs<RecordType>()->getDecl();
 406
 407   DeclarationName N = DeclarationName::getFromOpaquePtr(Name);
 408   for (Path.Decls = BaseRecord->lookup(N);
 409        Path.Decls.first != Path.Decls.second;
 410        ++Path.Decls.first) {
 411     // FIXME: Refactor the "is it a nested-name-specifier?" check
 412     if (isa<TypedefDecl>(*Path.Decls.first) ||
 413         (*Path.Decls.first)->isInIdentifierNamespace(IDNS_Tag))
 414       return true;
 415   }
 416
 417   return false;
 418 }