Make iteration over the DeclContext::lookup_result safe.

[v.g.vassilev]

Summary

The idiom:

DeclContext::lookup_result R = DeclContext::lookup(Name);
for (auto *D : R) {}

is not safe when in the loop body we trigger deserialization from an AST file. The deserialization can insert new declarations in the StoredDeclsList whose underlying type is a vector. When the vector decides to reallocate its storage the pointer we hold becomes invalid.

This patch replaces a SmallVector with an std::list. The current approach stores a SmallVector<NamedDecl*, 4> which is around 8 pointers. The linked list is 3, 5, or 7. We do better in terms of memory usage for small cases (and worse in terms of locality -- the linked list entries won't be near each other, but will be near their corresponding declarations, and we were going to fetch those memory pages anyway). For larger cases: the vector uses a doubling strategy for reallocation, so will generally be between half-full and full. Let's say it's 75% full on average, so there's N * 4/3 + 4 pointers' worth of space allocated currently and will be 2N pointers with the linked list. So we break even when there are N=6 entries and slightly lose in terms of memory usage after that. We suspect that's still a win on average.

Many thanks to @rsmith.

[v.g.vassilev]

Take another approach at solving this issue. Instead we are making the lookup_result safe.

[v.g.vassilev]

Invert the diff, fix a typo.

[v.g.vassilev]

clang/include/clang/AST/DeclBase.h

1275 ↗

(On Diff #306881)

I could not get rid of the now slow size() operation because in some cases we had if (Lookup1.size() == Lookup2.size())...

[rsmith]

clang/include/clang/AST/DeclContextInternals.h

36 ↗

(On Diff #306881)

It's not reasonable to use std::list for this; it will introduce too much allocation overhead.

Instead, how about a representation such as:

struct ListNode;
using Decls = llvm::PointerUnion<NamedDecl*, ListNode*>;
struct ListNode {
  NamedDecl *D;
  Decls Rest;
};

using DeclsAndHasExternalTy = llvm::PointerIntPair<Decls, 1, bool>;
DeclsAndHasExternalTy Data;

190–229 ↗

(On Diff #306881)

I think we should remove all assumptions about the order of declarations in a DeclContextLookupResult. The invariants maintained here can be expensive and are almost never useful.

clang/lib/Sema/SemaDeclCXX.cpp

15078–15089

The assumption made by this code was wrong, and is already fixed in trunk; you need to rebase.

clang/lib/Sema/SemaObjCProperty.cpp

1150–1151 ↗

(On Diff #306881)

This should presumably be a loop over the lookup results instead of assuming that the property decl, if it exists, will be the first declaration.

clang/lib/Sema/SemaTemplateInstantiate.cpp

3415–3417 ↗

(On Diff #306881)

This should be a loop over the results looking for the FieldDecl. (There can also be a TagDecl with the same name in the same scope.)

[v.g.vassilev]

Upload the current changes. I need to update the users such as lldb, clang-tools-extra and clangd. It has some rough edges wrt modules.

[rsmith]

clang/include/clang/AST/DeclBase.h

1238–1241 ↗

(On Diff #310217)

I think we never need to allocate a ListNode unless we have two or more declarations to track, so a ListNode can never be empty and neither D nor Rest can ever be null.

1268–1274 ↗

(On Diff #310217)

This doesn't look correct for a non-const iterator: modifying the result of this will modify the ListNode for all but the last list entry, but will modify only the data inside the iterator for the last item in the list.

Can we make this strictly a const iterator? I would hope people aren't mutating the lookup results they get back from DeclContext lookups :) We can open-code the list traversal in HandleRedeclaration.

1304–1313 ↗

(On Diff #310217)

Do we need this operation? It would be more efficient to support only push_front.

1304–1335 ↗

(On Diff #310217)

I don't think we should provide any of the operations to mutate a ListNode in DeclBase.h. Instead, how about we make StoredDeclsList a friend and move all this stuff to there?

1306 ↗

(On Diff #310217)

This should be allocated on the ASTContext's allocator.

1372 ↗

(On Diff #310217)

We should move this operation out of DeclContextLookupResult and give it a name that better expresses its purpose (eg: is an inline namespace qualifier necessary to disambiguate?).

How about moving this to a function such as:

bool NamespaceDecl::isRedundantInlineQualifierFor(DeclarationName Name) {
  if (!isInline())
    return false;
  auto X = lookup(Name);
  auto Y = getParent()->lookup(Name);
  return std::distance(X.begin(), X.end()) == std::distance(Y.begin(), Y.end());
}

... used as (for example):

-    if (Policy.SuppressInlineNamespace && NS->isInline() && NameInScope &&
-        DC->getParent()->lookup(NameInScope).equals(DC->lookup(NameInScope)))
+    if (Policy.SuppressInlineNamespace && NameInScope &&
+        NS->isRedundantInlineQualifierFor(NameInScope))

clang/include/clang/AST/DeclContextInternals.h

87–95 ↗

(On Diff #310217)

We don't need this complication with the new model; you should be able to replace this with Data.setInt(1);.

100 ↗

(On Diff #310217)

We used to clear the "has external decls" flag here. Should we still do so, or was that a bug?

113 ↗

(On Diff #310217)

This previously did not clear the "has external decls" flag. Presumably it still should not do so.

120 ↗

(On Diff #310217)

This seems impossible now. (Previously we only removed one element and this was checking there were no duplicates, but the new implementation of erase removes all matching elements rather than stopping after the first one.)

182 ↗

(On Diff #310217)

Looks like we end up with one too many ListNodes along this path. When we go from one declaration to two, we need only one ListNode but will allocate two of them.

clang/lib/AST/DeclBase.cpp

1547–1551 ↗

(On Diff #310217)

It seems wasteful to check whether the element is in the list here -- we're performing two passes where we only need one. Can we remove the assertion from StoredDeclsMap::remove that the element is present there, and replace all of this with a call to Pos->second.remove(ND)?

1943–1946 ↗

(On Diff #310217)

Please consider replacing setOnlyValue and AddSubsequentDecl with a single addDecl function. The caller shouldn't care about whether StoredDeclsList has a special case for there being only one declaration.

clang/lib/AST/ExternalASTMerger.cpp

74–82 ↗

(On Diff #310217)

I think this comment also applies to the return nullptr above. Consider moving the comment to before the new if.

[v.g.vassilev]

Store current state, address some comments, a few bugs still to address...

[v.g.vassilev]

Minor typos, conciseness..

[v.g.vassilev]

Add documentation, resolve address comments, update in-tree clients.

We still have several failures due to diag locations which seem to stem from the current design. The current failures are -- https://paste.ubuntu.com/p/MJSCQgm26P/

[rsmith]

clang/include/clang/AST/ASTContext.h

654 ↗

(On Diff #314270)

Should we clear out Alloc->Rest here too?

clang/include/clang/AST/DeclBase.h

1226 ↗

(On Diff #314270)

1231 ↗

(On Diff #314270)

Consider renaming DeclListNode::DeclListIterator to DeclListNode::iterator. I don't think we benefit from having both a public name and a private name for it.

1256 ↗

(On Diff #314270)

I would expect it->x to mean the same as (*it).x (which is invalid), but it actually means (**it).x. Can you remove this, and replace the pointer type with void to indicate we don't support operator->?

1261–1262 ↗

(On Diff #314270)

Is this assert different from the previous one? Do we need both?

1265–1268 ↗

(On Diff #314270)

Looks like this can be simplified a little.

1300 ↗

(On Diff #314270)

This appears to be equivalent, and slightly simpler.

1309 ↗

(On Diff #314270)

Minor simplification, NFC.

1315 ↗

(On Diff #314270)

clang/include/clang/AST/DeclContextInternals.h

35 ↗

(On Diff #314270)

Can you give this a better name? Or remove it -- I'm not sure we need a typedef for this.

76–79 ↗

(On Diff #314270)

This seems to be adding the new declaration as the second-last declaration in the list, not as the first declaration as the name of the function suggests.

90–112 ↗

(On Diff #314270)

Maybe something like this.

109 ↗

(On Diff #314270)

We mostly maintain the invariant that the Rest pointer of a list node is not null. I think this is the only deviation from that, and it seems like we can address that here -- in this case, I think we want to remove and deallocate Prev, replacing it with its declaration. I'll suggest edits.

197–206 ↗

(On Diff #314270)

This can now be simplified.

212–214 ↗

(On Diff #314270)

I think this can be simplified too.

256–268 ↗

(On Diff #314270)

Looks like this will dump the same thing twice. I assume that's just for debugging and can be simplified?

clang/lib/ARCMigrate/ObjCMT.cpp

652–653 ↗

(On Diff #314270)

May as well simplify this further while we're here.

clang/lib/AST/CXXInheritance.cpp

390 ↗

(On Diff #314270)

The "uninitialized" E here makes me uncomfortable as a reader. Maybe we could add a static DeclContext::lookup_iterator::end() and use that here? (E = I.end() if you want to get a little cute with it.)

clang/lib/Sema/SemaObjCProperty.cpp

115–116 ↗

(On Diff #314270)

May as well use the shiny new toys :)

235–236 ↗

(On Diff #314270)

Can use find_first here too.

[v.g.vassilev]

Address most of the comments.

The current version of the patch causes the following failures -- https://paste.ubuntu.com/p/Z4yKpK6rXq/

They are three kinds:

• the order of the overload candidates depends on the lookup order -- I'd rather make the candidate set resilient to the lookup order if that's feasible
• CodeGen's multi version function support depends on the lookup order -- there we have some ordering that depends and we may be able to incorporate another criterion rather than adjusting the test failures (CodeGenModule::emitMultiVersionFunctions)
• ObjC redeclaration implementation goes into an infinite loop -- the new model assumes new declarations to be prepended in the StoredDeclsList. However, in ObjC redecls are modeled in the ASTContext and when we are done we try finding the decl we started from but we find it via getMethod doing a lookup (however we started writing the middle decl and we never hit the termination rule).

For a) we can adjust the test cases but

[v.g.vassilev]

clang/include/clang/AST/DeclBase.h

1261–1262 ↗

(On Diff #314270)

Indeed! That patch had too implementation versions already :)

clang/include/clang/AST/DeclContextInternals.h

90–112 ↗

(On Diff #314270)

For the time being I fail to integrate the proposed change. My current diff is :

diff --git a/clang/include/clang/AST/DeclContextInternals.h b/clang/include/clang/AST/DeclContextInternals.h
index 63acc1d4396a..6aec759d87f0 100644
--- a/clang/include/clang/AST/DeclContextInternals.h
+++ b/clang/include/clang/AST/DeclContextInternals.h
@@ -32,7 +32,6 @@ class DependentDiagnostic;
 /// An array of decls optimized for the common case of only containing
 /// one entry.
 class StoredDeclsList {
-  using DeclsTy = DeclListNode;
   using Decls = DeclListNode::Decls;
 
   /// A collection of declarations, with a flag to indicate if we have
@@ -62,7 +61,7 @@ class StoredDeclsList {
     // to the next to point to OldD. This way we save an extra allocation.
     if (NamedDecl *OldD = getAsDecl()) {
       //assert(OldD != ND && "list already contains decl");
-      DeclsTy *Node = C.AllocateDeclListNode(OldD);
+      DeclListNode *Node = C.AllocateDeclListNode(OldD);
       Node->Rest = ND;
       Data.setPointer(Node);
       return;
@@ -71,40 +70,38 @@ class StoredDeclsList {
     // (void)Vec;
     // assert(llvm::find(Vec, ND) == Vec.end() && "list still contains decl");
 
-    DeclsTy *Node = C.AllocateDeclListNode(ND);
-    // DeclsTy *Cur = getAsList();
-    // while(Cur->Rest.dyn_cast<DeclsTy*>())
-    //   Cur = Cur->Rest.get<DeclsTy*>();
-    // Node->Rest = Cur->Rest;
-    // Cur->Rest = Node;
+    DeclListNode *Node = C.AllocateDeclListNode(ND);
     Node->Rest = Data.getPointer();
     Data.setPointer(Node);
   }
 
   template<typename Pred>
   void erase_if(Pred pred) {
-    assert(getAsList() && "Not in list mode!");
     ASTContext &C = getASTContext();
-    for (Decls N = Data.getPointer(), Prev = N; N; ) {
-      if (DeclsTy *L = N.dyn_cast<DeclsTy*>()) {
+    for (Decls N = Data.getPointer(), *Prev = nullptr; N; ) {
+      if (DeclListNode *L = N.dyn_cast<DeclListNode*>()) {
         if (pred(L->D)) {
-          if (L == getAsList())
-            Data.setPointer(L->Rest);
+          if (Prev)
+            Prev->get<DeclListNode*>()->Rest = L->Rest;
           else
-            Prev.get<DeclsTy*>()->Rest = L->Rest;
+            Data.setPointer(L->Rest);
           N = L->Rest;
           C.DeallocateDeclListNode(L);
         } else {
           N = L->Rest;
-          Prev = L;
+          if (Prev)
+            Prev = &Prev->get<DeclListNode*>()->Rest;
         }
       } else {
         NamedDecl *ND = N.get<NamedDecl*>();
         if (pred(ND)) {
-          if (getAsDecl())
+          if (Prev) {
+            DeclListNode *PrevNode = Prev->get<DeclListNode*>();
+            *Prev = PrevNode->D;
+            C.DeallocateDeclListNode(PrevNode);
+          } else {
             Data.setPointer(nullptr);
-          else
-            Prev.get<DeclsTy*>()->Rest = nullptr;
+          }
         }
         break;
       }
@@ -132,8 +129,8 @@ public:
     // If this is a list-form, free the list.
     ASTContext &C = getASTContext();
     Decls List = Data.getPointer();
-    while(List.is<DeclsTy*>()) {
-      DeclsTy *ToDealloc = List.get<DeclsTy*>();
+    while (List.is<DeclListNode*>()) {
+      DeclListNode *ToDealloc = List.get<DeclListNode*>();
       List = ToDealloc->Rest;
       C.DeallocateDeclListNode(ToDealloc);
     }
@@ -167,8 +164,8 @@ public:
     return getAsListAndHasExternal().getPointer().dyn_cast<NamedDecl *>();
   }
 
-  DeclsTy *getAsList() const {
-    return getAsListAndHasExternal().getPointer().dyn_cast<DeclsTy*>();
+  DeclListNode *getAsList() const {
+    return getAsListAndHasExternal().getPointer().dyn_cast<DeclListNode*>();
   }
 
   bool hasExternalDecls() const {
@@ -192,16 +189,10 @@ public:
 
   /// Remove any declarations which were imported from an external AST source.
   void removeExternalDecls() {
-    if (isNull()) {
-      // Nothing to do.
-    } else if (NamedDecl *Singleton = getAsDecl()) {
-      if (Singleton->isFromASTFile())
-        *this = StoredDeclsList();
-    } else {
+    if (!isNull())
       erase_if([](NamedDecl *ND){ return ND->isFromASTFile(); });
-      // Don't have any external decls any more.
-      Data.setInt(0);
-    }
+    // Don't have any external decls any more.
+    Data.setInt(0);
   }
 
   /// getLookupResult - Return an array of all the decls that this list
@@ -222,7 +213,7 @@ public:
     }
 
     // Determine if this declaration is actually a redeclaration.
-    for (DeclsTy* N = getAsList(); N; N = N->Rest.dyn_cast<DeclsTy*>()) {
+    for (auto N = getAsList(); N; N = N->Rest.dyn_cast<DeclListNode*>()) {
       if (D->declarationReplaces(N->D, IsKnownNewer)) {
         N->D = D;
         return true;

I get these failures -- https://paste.ubuntu.com/p/S6kzg5ngjy/

clang/lib/Sema/SemaObjCProperty.cpp

115–116 ↗

(On Diff #314270)

Good catch, thanks!

[rsmith]

clang/include/clang/AST/DeclBase.h

1238 ↗

(On Diff #319356)

I think this should be void to indicate that we don't support operator->.

clang/include/clang/AST/DeclContextInternals.h

61–69 ↗

(On Diff #319356)

This switches the order of the first two declarations in the list; after adding a few declarations in the order D1, D2, D3, D4, we'll have: {.D = D4, .Rest = {.D = D3, .Rest = {.D = D1, .Rest = D2}}}.

I think you'd get a more consistent ordering if you removed this if.

90–112 ↗

(On Diff #314270)

Suggested alternative: https://godbolt.org/z/szefda

[v.g.vassilev]

Address some of Richard's comments.

[v.g.vassilev]

Make visitation of multiversion functions independent on the lookup ordering; adjust tests.

[v.g.vassilev]

More fixes suggested by @rsmith

[v.g.vassilev]

Adjust the two tests I failed to merge.

[rsmith]

clang/include/clang/AST/DeclBase.h

1247 ↗

(On Diff #325595)

This triggers a compile error for me: this use of Ptr requires us to compute the alignment of a NamedDecl in order to determine how to lay out a PointerUnion<NamedDecl*, ...>, but we've not seen the definition of NamedDecl yet.

Adding this resolves the problem, but it seems a bit awkward and I wonder if there's a more elegant fix:

namespace llvm {
template <> struct PointerLikeTypeTraits<::clang::NamedDecl *> {
  static inline void *getAsVoidPointer(::clang::NamedDecl *P) { return P; }
                  
  static inline ::clang::NamedDecl *getFromVoidPointer(void *P) {
    return static_cast<::clang::NamedDecl *>(P);
  }
                              
  static constexpr int NumLowBitsAvailable = 3;
};                      
}

[v.g.vassilev]

Add changes proposed by @rsmith, add an assertion for duplicate entries.

[rsmith]

Thanks! Looks good. I've tested this on our side and it seems to work well. Let's land this and see if any further problems shake out.

[v.g.vassilev]

argh... I only now see the pre-merge suggestions -- almost all of them seem not super essential -- let me know if I should address them in a subsequent commit...

clang/include/clang/Sema/Sema.h

public:
   bool LookupInSuper(LookupResult &R, CXXRecordDecl *Class);
 
   void LookupOverloadedOperatorName(OverloadedOperatorKind Op, Scope *S,
                                     UnresolvedSetImpl &Functions);
 
   LabelDecl *LookupOrCreateLabel(IdentifierInfo *II, SourceLocation IdentLoc,
                                  SourceLocation GnuLabelLoc = SourceLocation());
 
-  DeclContextLookupResult LookupConstructors(CXXRecordDecl *Class);
+  void LookupConstructors(CXXRecordDecl *Class,
+                          llvm::SmallVectorImpl<NamedDecl*> &Constructors);
   CXXConstructorDecl *LookupDefaultConstructor(CXXRecordDecl *Class);
   CXXConstructorDecl *LookupCopyingConstructor(CXXRecordDecl *Class,
                                                unsigned Quals);
   CXXMethodDecl *LookupCopyingAssignment(CXXRecordDecl *Class, unsigned Quals,
                                          bool RValueThis, unsigned ThisQuals);
   CXXConstructorDecl *LookupMovingConstructor(CXXRecordDecl *Class,
                                               unsigned Quals);
   CXXMethodDecl *LookupMovingAssignment(CXXRecordDecl *Class, unsigned Quals,

clang/lib/Sema/SemaCodeComplete.cpp

QualType Sema::ProduceConstructorSignatureHelp(Scope *S, QualType Type,
   if (!RD)
     return Type;
 
   // FIXME: Provide support for member initializers.
   // FIXME: Provide support for variadic template constructors.
 
   OverloadCandidateSet CandidateSet(Loc, OverloadCandidateSet::CSK_Normal);
 
-  for (NamedDecl *C : LookupConstructors(RD)) {
+  llvm::SmallVector<NamedDecl*, 4> Ctors;
+  LookupConstructors(RD, Ctors);
+  for (NamedDecl *C : Ctors) {
     if (auto *FD = dyn_cast<FunctionDecl>(C)) {
       AddOverloadCandidate(FD, DeclAccessPair::make(FD, C->getAccess()), Args,
                            CandidateSet,
                            /*SuppressUserConversions=*/false,
                            /*PartialOverloading=*/true,
                            /*AllowExplicit*/ true);
     } else if (auto *FTD = dyn_cast<FunctionTemplateDecl>(C)) {
       AddTemplateOverloadCandidate(

clang/lib/Sema/SemaDeclCXX.cpp

         }
 
         // In this case, the name we introduce is the name of a derived class
         // constructor.
         auto *CurClass = cast<CXXRecordDecl>(CurContext);
         UsingName.setName(Context.DeclarationNames.getCXXConstructorName(
             Context.getCanonicalType(Context.getRecordType(CurClass))));
         UsingName.setNamedTypeInfo(nullptr);
-        for (auto *Ctor : LookupConstructors(RD))
+        llvm::SmallVector<NamedDecl*, 4> Ctors;
+        LookupConstructors(RD, Ctors);
+        for (auto *Ctor : Ctors)
           R.addDecl(Ctor);
         R.resolveKind();
       } else {
         // FIXME: Pick up all the declarations if we found an overloaded
         // function.
         UsingName.setName(ND->getDeclName());
         R.addDecl(ND);
       }

   // Maybe we haven't instantiated the in-class initializer. Go check the
   // pattern FieldDecl to see if it has one.
   CXXRecordDecl *ParentRD = cast<CXXRecordDecl>(Field->getParent());
 
   if (isTemplateInstantiation(ParentRD->getTemplateSpecializationKind())) {
     CXXRecordDecl *ClassPattern = ParentRD->getTemplateInstantiationPattern();
     DeclContext::lookup_result Lookup =
         ClassPattern->lookup(Field->getDeclName());
 
     // Lookup can return at most two results: the pattern for the field, or the
     // injected class name of the parent record. No other member can have the
     // same name as the field.
     // In modules mode, lookup can return multiple results (coming from
     // different modules).
     assert((getLangOpts().Modules || (!Lookup.empty() && Lookup.size() <= 2)) &&
            "more than two lookup results for field name");
     FieldDecl *Pattern = dyn_cast<FieldDecl>(Lookup[0]);
     if (!Pattern) {
       assert(isa<CXXRecordDecl>(Lookup[0]) &&
              "cannot have other non-field member with same name");
       for (auto L : Lookup)
         if (isa<FieldDecl>(L)) {
           Pattern = cast<FieldDecl>(L);
           break;
         }
       assert(Pattern && "We must have set the Pattern!");
     }
 

clang/lib/Sema/SemaExprCXX.cpp

if (T.isPODType(C) || T->isReferenceType() || T->isObjCLifetimeType())
       return true;
     if (CXXRecordDecl *RD = T->getAsCXXRecordDecl()) {
       if (RD->hasTrivialCopyConstructor() &&
           !RD->hasNonTrivialCopyConstructor())
         return true;
 
       bool FoundConstructor = false;
       unsigned FoundTQs;
-      for (const auto *ND : Self.LookupConstructors(RD)) {
+      llvm::SmallVector<NamedDecl*, 4> Ctors;
+      Self.LookupConstructors(RD, Ctors);
+      for (const auto *ND : Ctors) {
         // A template constructor is never a copy constructor.
         // FIXME: However, it may actually be selected at the actual overload
         // resolution point.
         if (isa<FunctionTemplateDecl>(ND->getUnderlyingDecl()))
           continue;
         // UsingDecl itself is not a constructor
         if (isa<UsingDecl>(ND))
           continue;
case UTT_HasNothrowConstructor:
     if (T.isPODType(C) || T->isObjCLifetimeType())
       return true;
     if (CXXRecordDecl *RD = C.getBaseElementType(T)->getAsCXXRecordDecl()) {
       if (RD->hasTrivialDefaultConstructor() &&
           !RD->hasNonTrivialDefaultConstructor())
         return true;
 
       bool FoundConstructor = false;
-      for (const auto *ND : Self.LookupConstructors(RD)) {
+      llvm::SmallVector<NamedDecl*, 4> Ctors;
+      Self.LookupConstructors(RD, Ctors);
+      for (const auto *ND : Ctors) {
         // FIXME: In C++0x, a constructor template can be a default constructor.
         if (isa<FunctionTemplateDecl>(ND->getUnderlyingDecl()))
           continue;
         // UsingDecl itself is not a constructor
         if (isa<UsingDecl>(ND))
           continue;
         auto *Constructor = cast<CXXConstructorDecl>(ND->getUnderlyingDecl());
         if (Constructor->isDefaultConstructor()) {

clang/lib/Sema/SemaInit.cpp

static bool hasCopyOrMoveCtorParam(ASTContext &Ctx,
   return Ctx.hasSameUnqualifiedType(ParmT, ClassT);
 }
 
 static OverloadingResult
 ResolveConstructorOverload(Sema &S, SourceLocation DeclLoc,
                            MultiExprArg Args,
                            OverloadCandidateSet &CandidateSet,
                            QualType DestType,
-                           DeclContext::lookup_result Ctors,
+                           const llvm::SmallVectorImpl<NamedDecl*>& Ctors,
                            OverloadCandidateSet::iterator &Best,
                            bool CopyInitializing, bool AllowExplicit,
                            bool OnlyListConstructors, bool IsListInit,
                            bool SecondStepOfCopyInit = false) {
   CandidateSet.clear(OverloadCandidateSet::CSK_InitByConstructor);
   CandidateSet.setDestAS(DestType.getQualifiers().getAddressSpace());
 
   for (NamedDecl *D : Ctors) {
static void TryConstructorInitialization(Sema &S,
   // Determine whether we are allowed to call explicit constructors or
   // explicit conversion operators.
   bool AllowExplicit = Kind.AllowExplicit() || IsListInit;
   bool CopyInitialization = Kind.getKind() == InitializationKind::IK_Copy;
 
   //   - Otherwise, if T is a class type, constructors are considered. The
   //     applicable constructors are enumerated, and the best one is chosen
   //     through overload resolution.
-  DeclContext::lookup_result Ctors = S.LookupConstructors(DestRecordDecl);
+  llvm::SmallVector<NamedDecl*, 4> Ctors;
+  S.LookupConstructors(DestRecordDecl, Ctors);
 
   OverloadingResult Result = OR_No_Viable_Function;
   OverloadCandidateSet::iterator Best;
   bool AsInitializerList = false;
 
   // C++11 [over.match.list]p1, per DR1467:
   //   When objects of non-aggregate type T are list-initialized, such that
   //   8.5.4 [dcl.init.list] specifies that overload resolution is performed
static OverloadingResult TryRefInitWithConversionFunction(
 
   const RecordType *T1RecordType = nullptr;
   if (AllowRValues && (T1RecordType = T1->getAs<RecordType>()) &&
       S.isCompleteType(Kind.getLocation(), T1)) {
     // The type we're converting to is a class type. Enumerate its constructors
     // to see if there is a suitable conversion.
     CXXRecordDecl *T1RecordDecl = cast<CXXRecordDecl>(T1RecordType->getDecl());
 
-    for (NamedDecl *D : S.LookupConstructors(T1RecordDecl)) {
+    llvm::SmallVector<NamedDecl*, 4> Ctors;
+    S.LookupConstructors(T1RecordDecl, Ctors);
+    for (NamedDecl *D : Ctors) {
       auto Info = getConstructorInfo(D);
       if (!Info.Constructor)
         continue;
 
       if (!Info.Constructor->isInvalidDecl() &&
           Info.Constructor->isConvertingConstructor(/*AllowExplicit*/true)) {
         if (Info.ConstructorTmpl)
           S.AddTemplateOverloadCandidate(
static void TryUserDefinedConversion(Sema &S,
   if (const RecordType *DestRecordType = DestType->getAs<RecordType>()) {
     // The type we're converting to is a class type. Enumerate its constructors
     // to see if there is a suitable conversion.
     CXXRecordDecl *DestRecordDecl
       = cast<CXXRecordDecl>(DestRecordType->getDecl());
 
     // Try to complete the type we're converting to.
     if (S.isCompleteType(Kind.getLocation(), DestType)) {
-      for (NamedDecl *D : S.LookupConstructors(DestRecordDecl)) {
+      llvm::SmallVector<NamedDecl*, 4> Ctors;
+      S.LookupConstructors(DestRecordDecl, Ctors);
+      for (NamedDecl *D : Ctors) {
         auto Info = getConstructorInfo(D);
         if (!Info.Constructor)
           continue;
 
         if (!Info.Constructor->isInvalidDecl() &&
             Info.Constructor->isConvertingConstructor(/*AllowExplicit*/true)) {
           if (Info.ConstructorTmpl)
             S.AddTemplateOverloadCandidate(
static ExprResult CopyObject(Sema &S,
   // Make sure that the type we are copying is complete.
   if (S.RequireCompleteType(Loc, T, diag::err_temp_copy_incomplete))
     return CurInit;
 
   // Perform overload resolution using the class's constructors. Per
   // C++11 [dcl.init]p16, second bullet for class types, this initialization
   // is direct-initialization.
   OverloadCandidateSet CandidateSet(Loc, OverloadCandidateSet::CSK_Normal);
-  DeclContext::lookup_result Ctors = S.LookupConstructors(Class);
+  llvm::SmallVector<NamedDecl*, 4> Ctors;
+  S.LookupConstructors(Class, Ctors);
 
   OverloadCandidateSet::iterator Best;
   switch (ResolveConstructorOverload(
       S, Loc, CurInitExpr, CandidateSet, T, Ctors, Best,
       /*CopyInitializing=*/false, /*AllowExplicit=*/true,
       /*OnlyListConstructors=*/false, /*IsListInit=*/false,
       /*SecondStepOfCopyInit=*/true)) {
   case OR_Success:
if (!Record)
     return;
 
   SourceLocation Loc = getInitializationLoc(Entity, CurInitExpr);
   if (S.Diags.isIgnored(diag::warn_cxx98_compat_temp_copy, Loc))
     return;
 
   // Find constructors which would have been considered.
   OverloadCandidateSet CandidateSet(Loc, OverloadCandidateSet::CSK_Normal);
-  DeclContext::lookup_result Ctors =
-      S.LookupConstructors(cast<CXXRecordDecl>(Record->getDecl()));
+  llvm::SmallVector<NamedDecl*, 4> Ctors;
+  S.LookupConstructors(cast<CXXRecordDecl>(Record->getDecl()), Ctors);
 
   // Perform overload resolution.
   OverloadCandidateSet::iterator Best;
   OverloadingResult OR = ResolveConstructorOverload(
       S, Loc, CurInitExpr, CandidateSet, CurInitExpr->getType(), Ctors, Best,
       /*CopyInitializing=*/false, /*AllowExplicit=*/true,
       /*OnlyListConstructors=*/false, /*IsListInit=*/false,
       /*SecondStepOfCopyInit=*/true);

clang/lib/Sema/SemaLookup.cpp

CXXConstructorDecl *Sema::LookupMovingConstructor(CXXRecordDecl *Class,
   SpecialMemberOverloadResult Result =
     LookupSpecialMember(Class, CXXMoveConstructor, Quals & Qualifiers::Const,
                         Quals & Qualifiers::Volatile, false, false, false);
 
   return cast_or_null<CXXConstructorDecl>(Result.getMethod());
 }
 
 /// Look up the constructors for the given class.
-DeclContext::lookup_result Sema::LookupConstructors(CXXRecordDecl *Class) {
+void Sema::LookupConstructors(CXXRecordDecl *Class,
+                              llvm::SmallVectorImpl<NamedDecl*> &Constructors) {
   // If the implicit constructors have not yet been declared, do so now.
   if (CanDeclareSpecialMemberFunction(Class)) {
     runWithSufficientStackSpace(Class->getLocation(), [&] {
       if (Class->needsImplicitDefaultConstructor())
         DeclareImplicitDefaultConstructor(Class);
       if (Class->needsImplicitCopyConstructor())
         DeclareImplicitCopyConstructor(Class);
       if (getLangOpts().CPlusPlus11 && Class->needsImplicitMoveConstructor())
         DeclareImplicitMoveConstructor(Class);
     });
   }
 
   CanQualType T = Context.getCanonicalType(Context.getTypeDeclType(Class));
   DeclarationName Name = Context.DeclarationNames.getCXXConstructorName(T);
-  return Class->lookup(Name);
+  // Working directly on R might trigger a deserialization, invalidating R if
+  // the underlying data structure needs to reallocate the storage.
+  DeclContext::lookup_result R = Class->lookup(Name);
+  Constructors.append(R.begin(), R.end());
 }
 
 /// Look up the copying assignment operator for the given class.
 CXXMethodDecl *Sema::LookupCopyingAssignment(CXXRecordDecl *Class,
                                              unsigned Quals, bool RValueThis,
                                              unsigned ThisQuals) {
   assert(!(Quals & ~(Qualifiers::Const | Qualifiers::Volatile)) &&
          "non-const, non-volatile qualifiers for copy assignment arg");
for (auto *NS : AssociatedNamespaces) {
     //     -- Any using-directives in the associated namespace are
     //        ignored.
     //
     //     -- Any namespace-scope friend functions declared in
     //        associated classes are visible within their respective
     //        namespaces even if they are not visible during an ordinary
     //        lookup (11.4).
     DeclContext::lookup_result R = NS->lookup(Name);
-    for (auto *D : R) {
+    // The loop might trigger a deserialization, invalidating R if the
+    // underlying data structure needs to reallocate the storage.
+    llvm::SmallVector<NamedDecl*, 8> RCopy(R.begin(), R.end());
+    for (auto *D : RCopy) {
       auto *Underlying = D;
       if (auto *USD = dyn_cast<UsingShadowDecl>(D))
         Underlying = USD->getTargetDecl();
 
       if (!isa<FunctionDecl>(Underlying) &&
           !isa<FunctionTemplateDecl>(Underlying))
         continue;
 

clang/lib/Sema/SemaOverload.cpp

 
 static OverloadingResult
 IsInitializerListConstructorConversion(Sema &S, Expr *From, QualType ToType,
                                        CXXRecordDecl *To,
                                        UserDefinedConversionSequence &User,
                                        OverloadCandidateSet &CandidateSet,
                                        bool AllowExplicit) {
   CandidateSet.clear(OverloadCandidateSet::CSK_InitByUserDefinedConversion);
-  for (auto *D : S.LookupConstructors(To)) {
+  llvm::SmallVector<NamedDecl*, 4> Ctors;
+  S.LookupConstructors(To, Ctors);
+  for (auto *D : Ctors) {
     auto Info = getConstructorInfo(D);
     if (!Info)
       continue;
 
     bool Usable = !Info.Constructor->isInvalidDecl() &&
                   S.isInitListConstructor(Info.Constructor);
     if (Usable) {
       // If the first argument is (a reference to) the target type,
if (!S.isCompleteType(From->getExprLoc(), ToType)) {
 
         // If we're list-initializing, we pass the individual elements as
         // arguments, not the entire list.
         Args = InitList->getInits();
         NumArgs = InitList->getNumInits();
         ListInitializing = true;
       }
 
-      for (auto *D : S.LookupConstructors(ToRecordDecl)) {
+      llvm::SmallVector<NamedDecl*, 4> Ctors;
+      S.LookupConstructors(ToRecordDecl, Ctors);
+      for (auto *D : Ctors) {
         auto Info = getConstructorInfo(D);
         if (!Info)
           continue;
 
         bool Usable = !Info.Constructor->isInvalidDecl();
         if (!ListInitializing)
           Usable = Usable && Info.Constructor->isConvertingConstructor(
                                  /*AllowExplicit*/ true);

clang/lib/Sema/SemaTemplate.cpp

void Sema::DeclareImplicitDeductionGuides(TemplateDecl *Template,
   if (BuildingDeductionGuides.isInvalid())
     return;
 
   // Convert declared constructors into deduction guide templates.
   // FIXME: Skip constructors for which deduction must necessarily fail (those
   // for which some class template parameter without a default argument never
   // appears in a deduced context).
   bool AddedAny = false;
-  for (NamedDecl *D : LookupConstructors(Transform.Primary)) {
+  llvm::SmallVector<NamedDecl*, 4> Ctors;
+  LookupConstructors(Transform.Primary, Ctors);
+  for (NamedDecl *D : Ctors) {
     D = D->getUnderlyingDecl();
     if (D->isInvalidDecl() || D->isImplicit())
       continue;
     D = cast<NamedDecl>(D->getCanonicalDecl());
 
     auto *FTD = dyn_cast<FunctionTemplateDecl>(D);
     auto *CD =
         dyn_cast_or_null<CXXConstructorDecl>(FTD ? FTD->getTemplatedDecl() : D);