From a54dffea61bb27f9812f5cc537eb512e30654473 Mon Sep 17 00:00:00 2001
From: Richard Smith <richard-llvm@metafoo.co.uk>
Date: Mon, 25 Apr 2016 19:28:08 +0000
Subject: [PATCH] Refactor traversal of bases in deduction of template
 parameters from base classes of an argument to use
 CXXRecordDecl::forallBases. Fix forallBases to only visit each base class
 once.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@267453 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/AST/CXXInheritance.cpp         | 15 ++++---
 lib/Sema/SemaTemplateDeduction.cpp | 71 +++++++++++-------------------
 2 files changed, 35 insertions(+), 51 deletions(-)

diff --git a/lib/AST/CXXInheritance.cpp b/lib/AST/CXXInheritance.cpp
index 6a6ca76a01..d1a2b435df 100644
--- a/lib/AST/CXXInheritance.cpp
+++ b/lib/AST/CXXInheritance.cpp
@@ -137,6 +137,7 @@ CXXRecordDecl::isCurrentInstantiation(const DeclContext *CurContext) const {
 bool CXXRecordDecl::forallBases(ForallBasesCallback BaseMatches,
                                 bool AllowShortCircuit) const {
   SmallVector<const CXXRecordDecl*, 8> Queue;
+  llvm::SmallPtrSet<const CXXRecordDecl*, 8> Enqueued;
 
   const CXXRecordDecl *Record = this;
   bool AllMatches = true;
@@ -158,12 +159,14 @@ bool CXXRecordDecl::forallBases(ForallBasesCallback BaseMatches,
         AllMatches = false;
         continue;
       }
-      
-      Queue.push_back(Base);
-      if (!BaseMatches(Base)) {
-        if (AllowShortCircuit) return false;
-        AllMatches = false;
-        continue;
+
+      if (Enqueued.insert(Base).second) {
+        Queue.push_back(Base);
+        if (!BaseMatches(Base)) {
+          if (AllowShortCircuit) return false;
+          AllMatches = false;
+          continue;
+        }
       }
     }
 
diff --git a/lib/Sema/SemaTemplateDeduction.cpp b/lib/Sema/SemaTemplateDeduction.cpp
index 59dc1da49a..f35dc30906 100644
--- a/lib/Sema/SemaTemplateDeduction.cpp
+++ b/lib/Sema/SemaTemplateDeduction.cpp
@@ -1454,54 +1454,35 @@ DeduceTemplateArgumentsByTypeMatch(Sema &S,
       //   otherwise fail. If they yield more than one possible deduced A, the
       //   type deduction fails.
 
-      // Reset the incorrectly deduced argument from above.
-      Deduced = DeducedOrig;
-
-      // Use data recursion to crawl through the list of base classes.
-      // Visited contains the set of nodes we have already visited, while
-      // ToVisit is our stack of records that we still need to visit.
-      llvm::SmallPtrSet<const RecordType *, 8> Visited;
-      SmallVector<const RecordType *, 8> ToVisit;
-      ToVisit.push_back(RecordT);
       bool Successful = false;
-      while (!ToVisit.empty()) {
-        // Retrieve the next class in the inheritance hierarchy.
-        const RecordType *NextT = ToVisit.pop_back_val();
-
-        // If we have already seen this type, skip it.
-        if (!Visited.insert(NextT).second)
-          continue;
-
-        // If this is a base class, try to perform template argument
-        // deduction from it.
-        if (NextT != RecordT) {
-          TemplateDeductionInfo BaseInfo(Info.getLocation());
-          Sema::TemplateDeductionResult BaseResult =
-              DeduceTemplateArguments(S, TemplateParams, SpecParam,
-                                      QualType(NextT, 0), BaseInfo, Deduced);
-
-          // If template argument deduction for this base was successful,
-          // note that we had some success. Otherwise, ignore any deductions
-          // from this base class.
-          if (BaseResult == Sema::TDK_Success) {
-            Successful = true;
-            DeducedOrig.clear();
-            DeducedOrig.append(Deduced.begin(), Deduced.end());
-            Info.Param = BaseInfo.Param;
-            Info.FirstArg = BaseInfo.FirstArg;
-            Info.SecondArg = BaseInfo.SecondArg;
-          } else
-            Deduced = DeducedOrig;
+      RecordT->getAsCXXRecordDecl()->forallBases([&](
+          const CXXRecordDecl *Base) {
+        // Start with a fresh copy of the old deduced arguments.
+        SmallVector<DeducedTemplateArgument, 8> DeducedBase(DeducedOrig.begin(),
+                                                            DeducedOrig.end());
+
+        TemplateDeductionInfo BaseInfo(Info.getLocation());
+        Sema::TemplateDeductionResult BaseResult =
+            DeduceTemplateArguments(S, TemplateParams, SpecParam,
+                                    S.Context.getRecordType(Base),
+                                    BaseInfo, DeducedBase);
+
+        // If template argument deduction for this base was successful,
+        // note that we had some success. Otherwise, ignore any deductions
+        // from this base class.
+        if (BaseResult == Sema::TDK_Success) {
+          // FIXME: If we've already been successful, deduction should fail
+          // due to ambiguity.
+          Successful = true;
+          Deduced.swap(DeducedBase);
+          Info.Param = BaseInfo.Param;
+          Info.FirstArg = BaseInfo.FirstArg;
+          Info.SecondArg = BaseInfo.SecondArg;
         }
 
-        // Visit base classes
-        CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl());
-        for (const auto &Base : Next->bases()) {
-          assert(Base.getType()->isRecordType() &&
-                 "Base class that isn't a record?");
-          ToVisit.push_back(Base.getType()->getAs<RecordType>());
-        }
-      }
+        // Keep going.
+        return true;
+      });
 
       if (Successful)
         return Sema::TDK_Success;
-- 
2.40.0