First non-embarrassing cut at checking for ambiguous derived-to-base

conversions.

Added PerformImplicitConversion, which follows an implicit conversion sequence
computed by TryCopyInitialization and actually performs the implicit
conversions, including the extra check for ambiguity mentioned above.

llvm-svn: 58071

1 files changed, 151 insertions, 6 deletions

diff --git a/clang/lib/Sema/SemaInherit.cpp b/clang/lib/Sema/SemaInherit.cpp
index 6890dbfc643..256ee24e1c9 100644
--- a/clang/lib/Sema/SemaInherit.cpp
+++ b/clang/lib/Sema/SemaInherit.cpp
@@ -14,19 +14,56 @@
 //===----------------------------------------------------------------------===//
 
 #include "Sema.h"
+#include "SemaInherit.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/DeclCXX.h"
+#include "clang/AST/Type.h"
+#include "clang/AST/TypeOrdering.h"
+#include "clang/Basic/Diagnostic.h"
+#include <memory>
+#include <set>
+#include <string>
 
 namespace clang {
 
+/// isAmbiguous - Determines whether the set of paths provided is
+/// ambiguous, i.e., there are two or more paths that refer to
+/// different base class subobjects of the same type. BaseType must be
+/// an unqualified, canonical class type.
+bool BasePaths::isAmbiguous(QualType BaseType) {
+  std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
+  return Subobjects.second + (Subobjects.first? 1 : 0) > 1;
+}
+
+/// clear - Clear out all prior path information.
+void BasePaths::clear() {
+  Paths.clear();
+  ClassSubobjects.clear();
+  ScratchPath.clear();
+}
+
+/// IsDerivedFrom - Determine whether the class type Derived is
+/// derived from the class type Base, ignoring qualifiers on Base and
+/// Derived. This routine does not assess whether an actual conversion
+/// from a Derived* to a Base* is legal, because it does not account
+/// for ambiguous conversions or conversions to private/protected bases.
+bool Sema::IsDerivedFrom(QualType Derived, QualType Base) {
+  BasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/false);
+  return IsDerivedFrom(Derived, Base, Paths);
+}
+
 /// IsDerivedFrom - Determine whether the class type Derived is
 /// derived from the class type Base, ignoring qualifiers on Base and
 /// Derived. This routine does not assess whether an actual conversion
 /// from a Derived* to a Base* is legal, because it does not account
 /// for ambiguous conversions or conversions to private/protected
-/// bases.
-bool Sema::IsDerivedFrom(QualType Derived, QualType Base)
-{
+/// bases. This routine will use Paths to determine if there are
+/// ambiguous paths (if @c Paths.isFindingAmbiguities()) and record
+/// information about all of the paths (if
+/// @c Paths.isRecordingPaths()).
+bool Sema::IsDerivedFrom(QualType Derived, QualType Base, BasePaths &Paths) {
+  bool FoundPath = false;
+  
   Derived = Context.getCanonicalType(Derived).getUnqualifiedType();
   Base = Context.getCanonicalType(Base).getUnqualifiedType();
   
@@ -41,12 +78,120 @@ bool Sema::IsDerivedFrom(QualType Derived, QualType Base)
       = static_cast<const CXXRecordDecl *>(DerivedType->getDecl());
     for (CXXRecordDecl::base_class_const_iterator BaseSpec = Decl->bases_begin();
          BaseSpec != Decl->bases_end(); ++BaseSpec) {
-      if (Context.getCanonicalType(BaseSpec->getType()) == Base
-          || IsDerivedFrom(BaseSpec->getType(), Base))
-        return true;
+      // Find the record of the base class subobjects for this type.
+      QualType BaseType = Context.getCanonicalType(BaseSpec->getType());
+      BaseType = BaseType.getUnqualifiedType();
+      
+      // Determine whether we need to visit this base class at all,
+      // updating the count of subobjects appropriately.
+      std::pair<bool, unsigned>& Subobjects = Paths.ClassSubobjects[BaseType];
+      bool VisitBase = true;
+      if (BaseSpec->isVirtual()) {
+        VisitBase = !Subobjects.first;
+        Subobjects.first = true;
+      } else
+        ++Subobjects.second;
+
+      if (Paths.isRecordingPaths()) {
+        // Add this base specifier to the current path.
+        BasePathElement Element;
+        Element.Base = &*BaseSpec;
+        if (BaseSpec->isVirtual())
+          Element.SubobjectNumber = 0;
+        else
+          Element.SubobjectNumber = Subobjects.second;
+        Paths.ScratchPath.push_back(Element);
+      }
+
+      if (Context.getCanonicalType(BaseSpec->getType()) == Base) {
+        // We've found the base we're looking for.
+        FoundPath = true;
+        if (Paths.isRecordingPaths()) {
+          // We have a path. Make a copy of it before moving on.
+          Paths.Paths.push_back(Paths.ScratchPath);
+        } else if (!Paths.isFindingAmbiguities()) {
+          // We found a path and we don't care about ambiguities;
+          // return immediately.
+          return FoundPath;
+        }
+      } else if (VisitBase && IsDerivedFrom(BaseSpec->getType(), Base, Paths)) {
+        // There is a path to the base we want. If we're not
+        // collecting paths or finding ambiguities, we're done.
+        FoundPath = true;
+        if (!Paths.isFindingAmbiguities())
+          return FoundPath;
+      }
+
+      // Pop this base specifier off the current path (if we're
+      // collecting paths).
+      if (Paths.isRecordingPaths())
+        Paths.ScratchPath.pop_back();
     }
   }
 
+  return FoundPath;
+}
+
+/// CheckDerivedToBaseConversion - Check whether the Derived-to-Base
+/// conversion (where Derived and Base are class types) is
+/// well-formed, meaning that the conversion is unambiguous (and
+/// FIXME: that all of the base classes are accessible). Returns true
+/// and emits a diagnostic if the code is ill-formed, returns false
+/// otherwise. Loc is the location where this routine should point to
+/// if there is an error, and Range is the source range to highlight
+/// if there is an error.
+bool 
+Sema::CheckDerivedToBaseConversion(SourceLocation Loc, SourceRange Range,
+                                   QualType Derived, QualType Base) {
+  // First, determine whether the path from Derived to Base is
+  // ambiguous. This is slightly more expensive than checking whether
+  // the Derived to Base conversion exists, because here we need to
+  // explore multiple paths to determine if there is an ambiguity.
+  BasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/false);
+  bool DerivationOkay = IsDerivedFrom(Derived, Base, Paths);
+  assert(DerivationOkay && "Can only be used with a derived-to-base conversion");
+  if (!DerivationOkay)
+    return true;
+
+  if (Paths.isAmbiguous(Context.getCanonicalType(Base).getUnqualifiedType())) {
+    // We know that the derived-to-base conversion is
+    // ambiguous. Perform the derived-to-base search just one more
+    // time to compute all of the possible paths so that we can print
+    // them out. This is more expensive than any of the previous
+    // derived-to-base checks we've done, but at this point we know
+    // we'll be issuing a diagnostic so performance isn't as much of
+    // an issue.
+    Paths.clear();
+    Paths.setRecordingPaths(true);
+    bool StillOkay = IsDerivedFrom(Derived, Base, Paths);
+    assert(StillOkay && "Can only be used with a derived-to-base conversion");
+    if (!StillOkay)
+      return true;
+
+    // Build up a textual representation of the ambiguous paths, e.g.,
+    // D -> B -> A, that will be used to illustrate the ambiguous
+    // conversions in the diagnostic. We only print one of the paths
+    // to each base class subobject.
+    std::string PathDisplayStr;
+    std::set<unsigned> DisplayedPaths;
+    for (BasePaths::paths_iterator Path = Paths.begin(); 
+         Path != Paths.end(); ++Path) {
+      if (DisplayedPaths.insert(Path->back().SubobjectNumber).second) {
+        // We haven't displayed a path to this particular base
+        // class subobject yet.
+        PathDisplayStr += "\n    ";
+        PathDisplayStr += Derived.getAsString();
+        for (BasePath::const_iterator Element = Path->begin(); 
+             Element != Path->end(); ++Element)
+          PathDisplayStr += " -> " + Element->Base->getType().getAsString(); 
+      }
+    }
+
+    Diag(Loc, diag::err_ambiguous_derived_to_base_conv,
+         Derived.getAsString(), Base.getAsString(), PathDisplayStr, Range);
+    return true;
+  }
+
   return false;
 }