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

1305–1306

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

34–35

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;

266–295

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

15105–15111

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

clang/lib/Sema/SemaObjCProperty.cpp

1144–1145

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

3421–3424

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

1234–1237

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.

1249–1255

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.

1285–1294

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

1285–1316

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?

1287

This should be allocated on the ASTContext's allocator.

1327

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

146–147

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

146–147

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

152

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

152

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.)

272–273

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

1508–1509

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)?

1900–1901

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

73–81

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

666

Should we clear out Alloc->Rest here too?

clang/include/clang/AST/DeclBase.h

1227

1232

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.

1251–1257

This appears to be equivalent, and slightly simpler.

1257

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->?

1262–1263

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

1266–1269

Looks like this can be simplified a little.

1286

Minor simplification, NFC.

1306

clang/include/clang/AST/DeclContextInternals.h

35

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

75–78

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.

89–111

Maybe something like this.

108

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.

156–160

This can now be simplified.

162–212

I think this can be simplified too.

290–302

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

650–652

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

clang/lib/AST/CXXInheritance.cpp

390

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

114–115

May as well use the shiny new toys :)

233–234

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

1262–1263

Indeed! That patch had too implementation versions already :)

clang/include/clang/AST/DeclContextInternals.h

89–111

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

114–115

Good catch, thanks!

[rsmith]

clang/include/clang/AST/DeclBase.h

1239

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

clang/include/clang/AST/DeclContextInternals.h

60–68

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.

89–111

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

1261

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-tools-extra/clangd/unittests/TestTU.cpp

 }
 
 const NamedDecl &findDecl(ParsedAST &AST, llvm::StringRef QName) {
   auto &Ctx = AST.getASTContext();
   auto LookupDecl = [&Ctx](const DeclContext &Scope,
                            llvm::StringRef Name) -> const NamedDecl & {
     auto LookupRes = Scope.lookup(DeclarationName(&Ctx.Idents.get(Name)));
     assert(!LookupRes.empty() && "Lookup failed");
-    assert(LookupRes.size() == 1 && "Lookup returned multiple results");
+    assert(LookupRes.isSingleResult() && "Lookup returned multiple results");
     return *LookupRes.front();
   };
 
   const DeclContext *Scope = Ctx.getTranslationUnitDecl();
 
   StringRef Cur, Rest;
   for (std::tie(Cur, Rest) = QName.split("::"); !Rest.empty();
        std::tie(Cur, Rest) = Rest.split("::")) {

clang/include/clang/AST/ASTContext.h

private:
   bool AddrSpaceMapMangling;
 
   const TargetInfo *Target = nullptr;
   const TargetInfo *AuxTarget = nullptr;
   clang::PrintingPolicy PrintingPolicy;
   std::unique_ptr<interp::Context> InterpContext;
   std::unique_ptr<ParentMapContext> ParentMapCtx;
 
+  /// Keeps track of the deallocated DeclListNodes for future reuse.
+  DeclListNode *ListNodeFreeList = nullptr;
+
 public:
   IdentifierTable &Idents;
   SelectorTable &Selectors;
   Builtin::Context &BuiltinInfo;
   mutable DeclarationNameTable DeclarationNames;
   IntrusiveRefCntPtr<ExternalASTSource> ExternalSource;
   ASTMutationListener *Listener = nullptr;
 
public:
   void *Allocate(size_t Size, unsigned Align = 8) const {
     return BumpAlloc.Allocate(Size, Align);
   }
   template <typename T> T *Allocate(size_t Num = 1) const {
     return static_cast<T *>(Allocate(Num * sizeof(T), alignof(T)));
   }
   void Deallocate(void *Ptr) const {}
 
+  /// Allocates a \c DeclListNode or returns one from the \c ListNodeFreeList
+  /// pool.
+  DeclListNode *AllocateDeclListNode(clang::NamedDecl *ND) {
+    if (DeclListNode *Alloc = ListNodeFreeList) {
+      ListNodeFreeList = Alloc->Rest.dyn_cast<DeclListNode*>();
+      Alloc->D = ND;
+      Alloc->Rest = nullptr;
+      return Alloc;
+    }
+    return new (*this) DeclListNode(ND);
+  }
+  /// Deallcates a \c DeclListNode by returning it to the \c ListNodeFreeList
+  /// pool.
+  void DeallocateDeclListNode(DeclListNode *N) {
+    N->Rest = ListNodeFreeList;
+    ListNodeFreeList = N;
+  }
+
   /// Return the total amount of physical memory allocated for representing
   /// AST nodes and type information.
   size_t getASTAllocatedMemory() const {
     return BumpAlloc.getTotalMemory();
   }
 
   /// Return the total memory used for various side tables.
   size_t getSideTableAllocatedMemory() const;

clang/include/clang/AST/CXXInheritance.h

 public:
   /// The access along this inheritance path.  This is only
   /// calculated when recording paths.  AS_none is a special value
   /// used to indicate a path which permits no legal access.
   AccessSpecifier Access = AS_public;
 
   CXXBasePath() = default;
 
-  /// The set of declarations found inside this base class
-  /// subobject.
-  DeclContext::lookup_result Decls;
+  /// The declarations found inside this base class subobject.
+  DeclContext::lookup_iterator Decls;
 
   void clear() {
     SmallVectorImpl<CXXBasePathElement>::clear();
     Access = AS_public;
   }
 };
 
 /// BasePaths - Represents the set of paths from a derived class to

clang/include/clang/AST/Decl.h

bool isInline() const {
     return AnonOrFirstNamespaceAndInline.getInt();
   }
 
   /// Set whether this is an inline namespace declaration.
   void setInline(bool Inline) {
     AnonOrFirstNamespaceAndInline.setInt(Inline);
   }
 
+  /// Returns true if the inline qualifier for \c Name is redundant.
+  bool isRedundantInlineQualifierFor(DeclarationName Name) const {
+    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());
+  }
+
   /// Get the original (first) namespace declaration.
   NamespaceDecl *getOriginalNamespace();
 
   /// Get the original (first) namespace declaration.
   const NamespaceDecl *getOriginalNamespace() const;
 
   /// Return true if this declaration is an original (first) declaration
   /// of the namespace. This is false for non-original (subsequent) namespace

clang/include/clang/AST/DeclBase.h

 
 public:
   PrettyStackTraceDecl(const Decl *theDecl, SourceLocation L,
                        SourceManager &sm, const char *Msg)
       : TheDecl(theDecl), Loc(L), SM(sm), Message(Msg) {}
 
   void print(raw_ostream &OS) const override;
 };
+} // namespace clang
 
-/// The results of name lookup within a DeclContext. This is either a
-/// single result (with no stable storage) or a collection of results (with
-/// stable storage provided by the lookup table).
-class DeclContextLookupResult {
-  using ResultTy = ArrayRef<NamedDecl *>;
-
-  ResultTy Result;
-
-  // If there is only one lookup result, it would be invalidated by
-  // reallocations of the name table, so store it separately.
-  NamedDecl *Single = nullptr;
-
-  static NamedDecl *const SingleElementDummyList;
+// Required to determine the layout of the PointerUnion<NamedDecl*> before
+// seeing the NamedDecl definition being first used in DeclListNode::operator*.
+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;
+  };
+}
 
+namespace clang {
+/// A list storing NamedDecls in the lookup tables.
+class DeclListNode {
+  friend class ASTContext; // allocate, deallocate nodes.
+  friend class StoredDeclsList;
 public:
-  DeclContextLookupResult() = default;
-  DeclContextLookupResult(ArrayRef<NamedDecl *> Result)
-      : Result(Result) {}
-  DeclContextLookupResult(NamedDecl *Single)
-      : Result(SingleElementDummyList), Single(Single) {}
-
-  class iterator;
-
-  using IteratorBase =
-      llvm::iterator_adaptor_base<iterator, ResultTy::iterator,
-                                  std::random_access_iterator_tag, NamedDecl *>;
-
-  class iterator : public IteratorBase {
-    value_type SingleElement;
+  using Decls = llvm::PointerUnion<NamedDecl*, DeclListNode*>;
+  class iterator {
+    friend class DeclContextLookupResult;
+    friend class StoredDeclsList;
 
+    Decls Ptr;
+    iterator(Decls Node) : Ptr(Node) { }
   public:
-    explicit iterator(pointer Pos, value_type Single = nullptr)
-        : IteratorBase(Pos), SingleElement(Single) {}
+    using difference_type = ptrdiff_t;
+    using value_type = NamedDecl*;
+    using pointer = void;
+    using reference = value_type;
+    using iterator_category = std::forward_iterator_tag;
+
+    iterator() = default;
 
     reference operator*() const {
-      return SingleElement ? SingleElement : IteratorBase::operator*();
+      assert(Ptr && "dereferencing end() iterator");
+      if (DeclListNode *CurNode = Ptr.dyn_cast<DeclListNode*>())
+        return CurNode->D;
+      return Ptr.get<NamedDecl*>();
+    }
+    void operator->() const { } // Unsupported.
+    bool operator==(const iterator &X) const { return Ptr == X.Ptr; }
+    bool operator!=(const iterator &X) const { return Ptr != X.Ptr; }
+    inline iterator &operator++() { // ++It
+      assert(!Ptr.isNull() && "Advancing empty iterator");
+
+      if (DeclListNode *CurNode = Ptr.dyn_cast<DeclListNode*>())
+        Ptr = CurNode->Rest;
+      else
+        Ptr = nullptr;
+      return *this;
+    }
+    iterator operator++(int) { // It++
+      iterator temp = *this;
+      ++(*this);
+      return temp;
     }
-  };
+    // Enables the pattern for (iterator I =..., E = I.end(); I != E; ++I)
+    iterator end() { return iterator(); }
+  };
+private:
+  NamedDecl *D = nullptr;
+  Decls Rest = nullptr;
+  DeclListNode(NamedDecl *ND) : D(ND) {}
 
+/// The results of name lookup within a DeclContext.
+class DeclContextLookupResult {
+  using Decls = DeclListNode::Decls;
+
+  /// When in collection form, this is what the Data pointer points to.
+  Decls Result;
+
+public:
+  DeclContextLookupResult() = default;
+  DeclContextLookupResult(Decls Result) : Result(Result) {}
+
+  using iterator = DeclListNode::iterator;
   using const_iterator = iterator;
-  using pointer = iterator::pointer;
   using reference = iterator::reference;
 
-  iterator begin() const { return iterator(Result.begin(), Single); }
-  iterator end() const { return iterator(Result.end(), Single); }
+  iterator begin() { return iterator(Result); }
+  iterator end() { return iterator(); }
+  const_iterator begin() const {
+    return const_cast<DeclContextLookupResult*>(this)->begin();
+  }
+  const_iterator end() const { return iterator(); }
+
+  bool empty() const { return Result.isNull();  }
+  bool isSingleResult() const { return Result.dyn_cast<NamedDecl*>(); }
+  reference front() const { return *begin(); }
+
+  // Find the first declaration of the given type in the list. Note that this
+  // is not in general the earliest-declared declaration, and should only be
+  // used when it's not possible for there to be more than one match or where
+  // it doesn't matter which one is found.
+  template<class T> T *find_first() const {
+    for (auto *D : *this)
+      if (T *Decl = dyn_cast<T>(D))
+        return Decl;
 
-  bool empty() const { return Result.empty(); }
-  pointer data() const { return Single ? &Single : Result.data(); }
-  size_t size() const { return Single ? 1 : Result.size(); }
-  reference front() const { return Single ? Single : Result.front(); }
-  reference back() const { return Single ? Single : Result.back(); }
-  reference operator[](size_t N) const { return Single ? Single : Result[N]; }
-
-  // FIXME: Remove this from the interface
-  DeclContextLookupResult slice(size_t N) const {
-    DeclContextLookupResult Sliced = Result.slice(N);
-    Sliced.Single = Single;
-    return Sliced;
+    return nullptr;
   }
 };
 
 /// DeclContext - This is used only as base class of specific decl types that
 /// can act as declaration contexts. These decls are (only the top classes
 /// that directly derive from DeclContext are mentioned, not their subclasses):
 ///
 ///   TranslationUnitDecl
 ///   ExternCContext

clang/include/clang/AST/DeclContextInternals.h

 //===- DeclContextInternals.h - DeclContext Representation ------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines the data structures used in the implementation
 //  of DeclContext.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H
 #define LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H
 
+#include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclarationName.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/PointerUnion.h"
-#include "llvm/ADT/SmallVector.h"
 #include <algorithm>
 #include <cassert>
 
 namespace clang {
 
 class DependentDiagnostic;
 
 /// An array of decls optimized for the common case of only containing
 /// one entry.
-struct StoredDeclsList {
-  /// When in vector form, this is what the Data pointer points to.
-  using DeclsTy = SmallVector<NamedDecl *, 4>;
+class StoredDeclsList {
+  using Decls = DeclListNode::Decls;
 
   /// A collection of declarations, with a flag to indicate if we have
   /// further external declarations.
-  using DeclsAndHasExternalTy = llvm::PointerIntPair<DeclsTy *, 1, bool>;
+  using DeclsAndHasExternalTy = llvm::PointerIntPair<Decls, 1, bool>;
 
   /// The stored data, which will be either a pointer to a NamedDecl,
-  /// or a pointer to a vector with a flag to indicate if there are further
+  /// or a pointer to a list with a flag to indicate if there are further
   /// external declarations.
-  llvm::PointerUnion<NamedDecl *, DeclsAndHasExternalTy> Data;
+  DeclsAndHasExternalTy Data;
+
+  template<typename Fn>
+  void erase_if(Fn ShouldErase) {
+    Decls List = Data.getPointer();
+    if (!List)
+      return;
+    ASTContext &C = getASTContext();
+    DeclListNode::Decls NewHead = nullptr;
+    DeclListNode::Decls *NewLast = nullptr;
+    DeclListNode::Decls *NewTail = &NewHead;
+    while (true) {
+      if (!ShouldErase(*DeclListNode::iterator(List))) {
+        NewLast = NewTail;
+        *NewTail = List;
+        if (auto *Node = List.dyn_cast<DeclListNode*>()) {
+          NewTail = &Node->Rest;
+          List = Node->Rest;
+        } else {
+          break;
+        }
+      } else if (DeclListNode *N = List.dyn_cast<DeclListNode*>()) {
+        List = N->Rest;
+        C.DeallocateDeclListNode(N);
+      } else {
+        // We're discarding the last declaration in the list. The last node we
+        // want to keep (if any) will be of the form DeclListNode(D, <rest>);
+        // replace it with just D.
+        if (NewLast) {
+          DeclListNode *Node = NewLast->get<DeclListNode*>();
+          *NewLast = Node->D;
+          C.DeallocateDeclListNode(Node);
+        }
+        break;
+      }
+    }
+    Data.setPointer(NewHead);
+
+    assert(llvm::find_if(getLookupResult(), ShouldErase) ==
+           getLookupResult().end() && "Still exists!");
+  }
+
+  void erase(NamedDecl *ND) {
+    erase_if([ND](NamedDecl *D) { return D == ND; });
+  }
 
 public:
   StoredDeclsList() = default;
 
   StoredDeclsList(StoredDeclsList &&RHS) : Data(RHS.Data) {
-    RHS.Data = (NamedDecl *)nullptr;
+    RHS.Data.setPointer(nullptr);
+    RHS.Data.setInt(0);
+  }
+
+  void MaybeDeallocList() {
+    if (isNull())
+      return;
+    // If this is a list-form, free the list.
+    ASTContext &C = getASTContext();
+    Decls List = Data.getPointer();
+    while (DeclListNode *ToDealloc = List.dyn_cast<DeclListNode *>()) {
+      List = ToDealloc->Rest;
+      C.DeallocateDeclListNode(ToDealloc);
+    }
   }
 
   ~StoredDeclsList() {
-    // If this is a vector-form, free the vector.
-    if (DeclsTy *Vector = getAsVector())
-      delete Vector;
+    MaybeDeallocList();
   }
 
   StoredDeclsList &operator=(StoredDeclsList &&RHS) {
-    if (DeclsTy *Vector = getAsVector())
-      delete Vector;
+    MaybeDeallocList();
+
     Data = RHS.Data;
-    RHS.Data = (NamedDecl *)nullptr;
+    RHS.Data.setPointer(nullptr);
+    RHS.Data.setInt(0);
     return *this;
   }
 
-  bool isNull() const { return Data.isNull(); }
+  bool isNull() const { return Data.getPointer().isNull(); }
 
-  NamedDecl *getAsDecl() const {
-    return Data.dyn_cast<NamedDecl *>();
+  ASTContext &getASTContext() {
+    assert(!isNull() && "No ASTContext.");
+    if (NamedDecl *ND = getAsDecl())
+      return ND->getASTContext();
+    return getAsList()->D->getASTContext();
   }
 
-  DeclsAndHasExternalTy getAsVectorAndHasExternal() const {
-    return Data.dyn_cast<DeclsAndHasExternalTy>();
+  DeclsAndHasExternalTy getAsListAndHasExternal() const { return Data; }
+
+  NamedDecl *getAsDecl() const {
+    return getAsListAndHasExternal().getPointer().dyn_cast<NamedDecl *>();
   }
 
-  DeclsTy *getAsVector() const {
-    return getAsVectorAndHasExternal().getPointer();
+  DeclListNode *getAsList() const {
+    return getAsListAndHasExternal().getPointer().dyn_cast<DeclListNode*>();
   }
 
   bool hasExternalDecls() const {
-    return getAsVectorAndHasExternal().getInt();
+    return getAsListAndHasExternal().getInt();
   }
 
   void setHasExternalDecls() {
-    if (DeclsTy *Vec = getAsVector())
-      Data = DeclsAndHasExternalTy(Vec, true);
-    else {
-      DeclsTy *VT = new DeclsTy();
-      if (NamedDecl *OldD = getAsDecl())
-        VT->push_back(OldD);
-      Data = DeclsAndHasExternalTy(VT, true);
-    }
-  }
-
-  void setOnlyValue(NamedDecl *ND) {
-    assert(!getAsVector() && "Not inline");
-    Data = ND;
-    // Make sure that Data is a plain NamedDecl* so we can use its address
-    // at getLookupResult.
-    assert(*(NamedDecl **)&Data == ND &&
-           "PointerUnion mangles the NamedDecl pointer!");
+    Data.setInt(1);
   }
 
   void remove(NamedDecl *D) {
     assert(!isNull() && "removing from empty list");
-    if (NamedDecl *Singleton = getAsDecl()) {
-      assert(Singleton == D && "list is different singleton");
-      (void)Singleton;
-      Data = (NamedDecl *)nullptr;
-      return;
-    }
+    erase(D);
 
-    DeclsTy &Vec = *getAsVector();
-    DeclsTy::iterator I = llvm::find(Vec, D);
-    assert(I != Vec.end() && "list does not contain decl");
-    Vec.erase(I);
+  /// Remove any declarations which were imported from an external AST source.
+  void removeExternalDecls() {
+    erase_if([](NamedDecl *ND) { return ND->isFromASTFile(); });
 
-    assert(llvm::find(Vec, D) == Vec.end() && "list still contains decl");
+    // Don't have any pending external decls any more.
+    Data.setInt(0);
   }
 
-  /// 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 {
-      DeclsTy &Vec = *getAsVector();
-      Vec.erase(std::remove_if(Vec.begin(), Vec.end(),
-                               [](Decl *D) { return D->isFromASTFile(); }),
-                Vec.end());
-      // Don't have any external decls any more.
-      Data = DeclsAndHasExternalTy(&Vec, false);
-    }
-  }
+  void replaceExternalDecls(ArrayRef<NamedDecl*> Decls) {
+    // Remove all declarations that are either external or are replaced with
+    // external declarations.
+    erase_if([Decls](NamedDecl *ND) {
+      if (ND->isFromASTFile())
+        return true;
+      for (NamedDecl *D : Decls)
+        if (D->declarationReplaces(ND, /*IsKnownNewer=*/false))
+          return true;
+      return false;
+    });
 
-  /// getLookupResult - Return an array of all the decls that this list
-  /// represents.
-  DeclContext::lookup_result getLookupResult() {
-    if (isNull())
-      return DeclContext::lookup_result();
+    // Don't have any pending external decls any more.
+    Data.setInt(0);
 
-    // If we have a single NamedDecl, return it.
-    if (NamedDecl *ND = getAsDecl()) {
-      assert(!isNull() && "Empty list isn't allowed");
+    if (Decls.empty())
+      return;
 
-      // Data is a raw pointer to a NamedDecl*, return it.
-      return DeclContext::lookup_result(ND);
+    // Convert Decls into a list, in order.
+    ASTContext &C = Decls.front()->getASTContext();
+    DeclListNode::Decls DeclsAsList = Decls.back();
+    for (size_t I = Decls.size() - 1; I != 0; --I) {
+      DeclListNode *Node = C.AllocateDeclListNode(Decls[I - 1]);
+      Node->Rest = DeclsAsList;
+      DeclsAsList = Node;
     }
 
-    assert(getAsVector() && "Must have a vector at this point");
-    DeclsTy &Vector = *getAsVector();
+    DeclListNode::Decls Head = Data.getPointer();
+    if (Head.isNull()) {
+      Data.setPointer(DeclsAsList);
+      return;
+    }
 
-    // Otherwise, we have a range result.
-    return DeclContext::lookup_result(Vector);
+    // Find the end of the existing list.
+    // FIXME: It would be possible to preserve information from erase_if to
+    // avoid this rescan looking for the end of the list.
+    DeclListNode::Decls *Tail = &Head;
+    while (DeclListNode *Node = Tail->dyn_cast<DeclListNode *>())
+      Tail = &Node->Rest;
+
+    // Append the Decls.
+    DeclListNode *Node = C.AllocateDeclListNode(Tail->get<NamedDecl *>());
+    Node->Rest = DeclsAsList;
+    *Tail = Node;
+    Data.setPointer(Head);
+  }
+
+  /// Return an array of all the decls that this list represents.
+  DeclContext::lookup_result getLookupResult() const {
+    return DeclContext::lookup_result(Data.getPointer());
+  }
+
+  /// If this is a redeclaration of an existing decl, replace the old one with
+  /// D. Otherwise, append D.
+  void addOrReplaceDecl(NamedDecl *D) {
+    const bool IsKnownNewer = true;
+
+    if (isNull()) {
+      Data.setPointer(D);
+      return;
     }
 
-  /// HandleRedeclaration - If this is a redeclaration of an existing decl,
-  /// replace the old one with D and return true.  Otherwise return false.
-  bool HandleRedeclaration(NamedDecl *D, bool IsKnownNewer) {
     // Most decls only have one entry in their list, special case it.
     if (NamedDecl *OldD = getAsDecl()) {
-      if (!D->declarationReplaces(OldD, IsKnownNewer))
-        return false;
-      setOnlyValue(D);
-      return true;
+      if (D->declarationReplaces(OldD, IsKnownNewer)) {
+        Data.setPointer(D);
+        return;
       }
 
+      // Add D after OldD.
+      ASTContext &C = D->getASTContext();
+      DeclListNode *Node = C.AllocateDeclListNode(OldD);
+      Node->Rest = D;
+      Data.setPointer(Node);
+      return;
+    }
+
+    // FIXME: Move the assert before the single decl case when we fix the
+    // duplication coming from the ASTReader reading builtin types.
+    assert(!llvm::is_contained(getLookupResult(), D) && "Already exists!");
     // Determine if this declaration is actually a redeclaration.
-    DeclsTy &Vec = *getAsVector();
-    for (DeclsTy::iterator OD = Vec.begin(), ODEnd = Vec.end();
-         OD != ODEnd; ++OD) {
-      NamedDecl *OldD = *OD;
-      if (D->declarationReplaces(OldD, IsKnownNewer)) {
-        *OD = D;
-        return true;
+    for (DeclListNode *N = getAsList(); /*return in loop*/;
+         N = N->Rest.dyn_cast<DeclListNode *>()) {
+      if (D->declarationReplaces(N->D, IsKnownNewer)) {
+        N->D = D;
+        return;
       }
+      if (auto *ND = N->Rest.dyn_cast<NamedDecl *>()) {
+        if (D->declarationReplaces(ND, IsKnownNewer)) {
+          N->Rest = D;
+          return;
         }
 
-    return false;
+        // Add D after ND.
+        ASTContext &C = D->getASTContext();
+        DeclListNode *Node = C.AllocateDeclListNode(ND);
+        N->Rest = Node;
+        Node->Rest = D;
+        return;
+      }
+    }
   }
 
-  /// AddSubsequentDecl - This is called on the second and later decl when it is
-  /// not a redeclaration to merge it into the appropriate place in our list.
-  void AddSubsequentDecl(NamedDecl *D) {
-    assert(!isNull() && "don't AddSubsequentDecl when we have no decls");
+  /// Add a declaration to the list without checking if it replaces anything.
+  void prependDeclNoReplace(NamedDecl *D) {
+    if (isNull()) {
+      Data.setPointer(D);
+      return;
+    }
 
-    // If this is the second decl added to the list, convert this to vector
-    // form.
-    if (NamedDecl *OldD = getAsDecl()) {
-      DeclsTy *VT = new DeclsTy();
-      VT->push_back(OldD);
-      Data = DeclsAndHasExternalTy(VT, false);
-    }
-
-    DeclsTy &Vec = *getAsVector();
-
-    // Using directives end up in a special entry which contains only
-    // other using directives, so all this logic is wasted for them.
-    // But avoiding the logic wastes time in the far-more-common case
-    // that we're *not* adding a new using directive.
-
-    // Tag declarations always go at the end of the list so that an
-    // iterator which points at the first tag will start a span of
-    // decls that only contains tags.
-    if (D->hasTagIdentifierNamespace())
-      Vec.push_back(D);
-
-    // Resolved using declarations go at the front of the list so that
-    // they won't show up in other lookup results.  Unresolved using
-    // declarations (which are always in IDNS_Using | IDNS_Ordinary)
-    // follow that so that the using declarations will be contiguous.
-    else if (D->getIdentifierNamespace() & Decl::IDNS_Using) {
-      DeclsTy::iterator I = Vec.begin();
-      if (D->getIdentifierNamespace() != Decl::IDNS_Using) {
-        while (I != Vec.end() &&
-               (*I)->getIdentifierNamespace() == Decl::IDNS_Using)
-          ++I;
-      }
-      Vec.insert(I, D);
-
-    // All other declarations go at the end of the list, but before any
-    // tag declarations.  But we can be clever about tag declarations
-    // because there can only ever be one in a scope.
-    } else if (!Vec.empty() && Vec.back()->hasTagIdentifierNamespace()) {
-      NamedDecl *TagD = Vec.back();
-      Vec.back() = D;
-      Vec.push_back(TagD);
-    } else
-      Vec.push_back(D);
+    ASTContext &C = D->getASTContext();
+    DeclListNode *Node = C.AllocateDeclListNode(D);
+    Node->Rest = Data.getPointer();
+    Data.setPointer(Node);
+  }
+
+  LLVM_DUMP_METHOD void dump() const {
+    Decls D = Data.getPointer();
+    if (!D) {
+      llvm::errs() << "<null>\n";
+      return;
+    }
+
+    while (true) {
+      if (auto *Node = D.dyn_cast<DeclListNode*>()) {
+        llvm::errs() << '[' << Node->D << "] -> ";
+        D = Node->Rest;
+      } else {
+        llvm::errs() << '[' << D.get<NamedDecl*>() << "]\n";
+        return;
+      }
+    }
   }
 };
 
 class StoredDeclsMap
     : public llvm::SmallDenseMap<DeclarationName, StoredDeclsList, 4> {
-public:
-  static void DestroyAll(StoredDeclsMap *Map, bool Dependent);
-
-private:
   friend class ASTContext; // walks the chain deleting these
   friend class DeclContext;
 
   llvm::PointerIntPair<StoredDeclsMap*, 1> Previous;
+public:
+  static void DestroyAll(StoredDeclsMap *Map, bool Dependent);
 };
 
 class DependentStoredDeclsMap : public StoredDeclsMap {
-public:
-  DependentStoredDeclsMap() = default;
-
-private:
   friend class DeclContext; // iterates over diagnostics
   friend class DependentDiagnostic;
 
   DependentDiagnostic *FirstDiagnostic = nullptr;
+public:
+  DependentStoredDeclsMap() = default;
 };
 
 } // namespace clang
 
 #endif // LLVM_CLANG_AST_DECLCONTEXTINTERNALS_H

clang/include/clang/Serialization/ASTWriter.h

 class ObjCInterfaceDecl;
 class PreprocessingRecord;
 class Preprocessor;
 struct QualifierInfo;
 class RecordDecl;
 class Sema;
 class SourceManager;
 class Stmt;
-struct StoredDeclsList;
+class StoredDeclsList;
 class SwitchCase;
 class TemplateParameterList;
 class Token;
 class TypeSourceInfo;
 
 /// Writes an AST file containing the contents of a translation unit.
 ///
 /// The ASTWriter class produces a bitstream containing the serialized

clang/lib/ARCMigrate/ObjCMT.cpp

ClassImplementsAllMethodsAndProperties(ASTContext &Ctx,
   // in class interface.
   bool HasAtleastOneRequiredProperty = false;
   if (const ObjCProtocolDecl *PDecl = Protocol->getDefinition())
     for (const auto *Property : PDecl->instance_properties()) {
       if (Property->getPropertyImplementation() == ObjCPropertyDecl::Optional)
         continue;
       HasAtleastOneRequiredProperty = true;
       DeclContext::lookup_result R = IDecl->lookup(Property->getDeclName());
-      if (R.size() == 0) {
+      if (R.empty()) {
         // Relax the rule and look into class's implementation for a synthesize
         // or dynamic declaration. Class is implementing a property coming from
         // another protocol. This still makes the target protocol as conforming.
         if (!ImpDecl->FindPropertyImplDecl(
                                   Property->getDeclName().getAsIdentifierInfo(),
                                   Property->getQueryKind()))
           return false;
-      }
-      else if (ObjCPropertyDecl *ClassProperty = dyn_cast<ObjCPropertyDecl>(R[0])) {
-          if ((ClassProperty->getPropertyAttributes()
-              != Property->getPropertyAttributes()) ||
-              !Ctx.hasSameType(ClassProperty->getType(), Property->getType()))
-            return false;
-      }
-      else
+      } else if (auto *ClassProperty = R.find_first<ObjCPropertyDecl>()) {
+        if ((ClassProperty->getPropertyAttributes() !=
+             Property->getPropertyAttributes()) ||
+      } else
         return false;
     }
 
   // At this point, all required properties in this protocol conform to those
   // declared in the class.
   // Check that class implements the required methods of the protocol too.
   bool HasAtleastOneRequiredMethod = false;
   if (const ObjCProtocolDecl *PDecl = Protocol->getDefinition()) {
     if (PDecl->meth_begin() == PDecl->meth_end())
       return HasAtleastOneRequiredProperty;
     for (const auto *MD : PDecl->methods()) {
       if (MD->isImplicit())
         continue;
       if (MD->getImplementationControl() == ObjCMethodDecl::Optional)
         continue;
       DeclContext::lookup_result R = ImpDecl->lookup(MD->getDeclName());
-      if (R.size() == 0)
+      if (R.empty())
         return false;
       bool match = false;
       HasAtleastOneRequiredMethod = true;
-      for (unsigned I = 0, N = R.size(); I != N; ++I)
-        if (ObjCMethodDecl *ImpMD = dyn_cast<ObjCMethodDecl>(R[0]))
+      for (NamedDecl *ND : R)
+        if (ObjCMethodDecl *ImpMD = dyn_cast<ObjCMethodDecl>(ND))
           if (Ctx.ObjCMethodsAreEqual(MD, ImpMD)) {
             match = true;
             break;
           }
       if (!match)
         return false;
     }
   }
   return HasAtleastOneRequiredProperty || HasAtleastOneRequiredMethod;

clang/lib/AST/ASTContext.cpp

 }
 
 void ASTContext::forEachMultiversionedFunctionVersion(
     const FunctionDecl *FD,
     llvm::function_ref<void(FunctionDecl *)> Pred) const {
   assert(FD->isMultiVersion() && "Only valid for multiversioned functions");
   llvm::SmallDenseSet<const FunctionDecl*, 4> SeenDecls;
   FD = FD->getMostRecentDecl();
+  // FIXME: The order of traversal here matters and depends on the order of
+  // lookup results, which happens to be (mostly) oldest-to-newest, but we
+  // shouldn't rely on that.
   for (auto *CurDecl :
        FD->getDeclContext()->getRedeclContext()->lookup(FD->getDeclName())) {
     FunctionDecl *CurFD = CurDecl->getAsFunction()->getMostRecentDecl();
     if (CurFD && hasSameType(CurFD->getType(), FD->getType()) &&
         std::end(SeenDecls) == llvm::find(SeenDecls, CurFD)) {
       SeenDecls.insert(CurFD);
       Pred(CurFD);
     }

clang/lib/AST/CXXInheritance.cpp

 
 static bool isOrdinaryMember(const NamedDecl *ND) {
   return ND->isInIdentifierNamespace(Decl::IDNS_Ordinary | Decl::IDNS_Tag |
                                      Decl::IDNS_Member);
 }
 
 static bool findOrdinaryMember(const CXXRecordDecl *RD, CXXBasePath &Path,
                                DeclarationName Name) {
-  Path.Decls = RD->lookup(Name);
-  for (NamedDecl *ND : Path.Decls)
-    if (isOrdinaryMember(ND))
+  Path.Decls = RD->lookup(Name).begin();
+  for (DeclContext::lookup_iterator I = Path.Decls, E = I.end(); I != E; ++I)
+    if (isOrdinaryMember(*I))
       return true;
 
   return false;
 }
 
 bool CXXRecordDecl::hasMemberName(DeclarationName Name) const {
   CXXBasePath P;
   if (findOrdinaryMember(this, P, Name))
std::vector<const NamedDecl *> CXXRecordDecl::lookupDependentName(
   CXXBasePaths Paths;
   Paths.setOrigin(this);
   if (!lookupInBases(
           [&](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
             return findOrdinaryMemberInDependentClasses(Specifier, Path, Name);
           },
           Paths, /*LookupInDependent=*/true))
     return Results;
-  for (const NamedDecl *ND : Paths.front().Decls) {
-    if (isOrdinaryMember(ND) && Filter(ND))
-      Results.push_back(ND);
+  for (DeclContext::lookup_iterator I = Paths.front().Decls, E = I.end();
+       I != E; ++I) {
+    if (isOrdinaryMember(*I) && Filter(*I))
+      Results.push_back(*I);
   }
   return Results;
 }
 
 void OverridingMethods::add(unsigned OverriddenSubobject,
                             UniqueVirtualMethod Overriding) {
   SmallVectorImpl<UniqueVirtualMethod> &SubobjectOverrides
     = Overrides[OverriddenSubobject];

clang/lib/AST/Decl.cpp

void NamedDecl::printNestedNameSpecifier(raw_ostream &OS,
   for (; Ctx; Ctx = Ctx->getParent()) {
     // Suppress anonymous namespace if requested.
     if (P.SuppressUnwrittenScope && isa<NamespaceDecl>(Ctx) &&
         cast<NamespaceDecl>(Ctx)->isAnonymousNamespace())
       continue;
 
     // Suppress inline namespace if it doesn't make the result ambiguous.
     if (P.SuppressInlineNamespace && Ctx->isInlineNamespace() && NameInScope &&
-        Ctx->lookup(NameInScope).size() ==
-            Ctx->getParent()->lookup(NameInScope).size())
+        cast<NamespaceDecl>(Ctx)->isRedundantInlineQualifierFor(NameInScope))
       continue;
 
     // Skip non-named contexts such as linkage specifications and ExportDecls.
     const NamedDecl *ND = dyn_cast<NamedDecl>(Ctx);
     if (!ND)
       continue;
 
     Contexts.push_back(Ctx);

clang/lib/AST/DeclBase.cpp

ExternalASTSource::SetExternalVisibleDeclsForName(const DeclContext *DC,
   ASTContext &Context = DC->getParentASTContext();
   StoredDeclsMap *Map;
   if (!(Map = DC->LookupPtr))
     Map = DC->CreateStoredDeclsMap(Context);
   if (DC->hasNeedToReconcileExternalVisibleStorage())
     DC->reconcileExternalVisibleStorage();
 
   StoredDeclsList &List = (*Map)[Name];
-
-  // Clear out any old external visible declarations, to avoid quadratic
-  // performance in the redeclaration checks below.
-  List.removeExternalDecls();
-
-  if (!List.isNull()) {
-    // We have both existing declarations and new declarations for this name.
-    // Some of the declarations may simply replace existing ones. Handle those
-    // first.
-    llvm::SmallVector<unsigned, 8> Skip;
-    for (unsigned I = 0, N = Decls.size(); I != N; ++I)
-      if (List.HandleRedeclaration(Decls[I], /*IsKnownNewer*/false))
-        Skip.push_back(I);
-    Skip.push_back(Decls.size());
-
-    // Add in any new declarations.
-    unsigned SkipPos = 0;
-    for (unsigned I = 0, N = Decls.size(); I != N; ++I) {
-      if (I == Skip[SkipPos])
-        ++SkipPos;
-      else
-        List.AddSubsequentDecl(Decls[I]);
-    }
-  } else {
-    // Convert the array to a StoredDeclsList.
-    for (auto *D : Decls) {
-      if (List.isNull())
-        List.setOnlyValue(D);
-      else
-        List.AddSubsequentDecl(D);
-    }
-  }
-
+  List.replaceExternalDecls(Decls);
   return List.getLookupResult();
 }
 
 DeclContext::decl_iterator DeclContext::decls_begin() const {
   if (hasExternalLexicalStorage())
     LoadLexicalDeclsFromExternalStorage();
   return decl_iterator(FirstDecl);
 }
if (isa<NamedDecl>(D)) {
     if (!ND->getDeclName())
       return;
 
     auto *DC = D->getDeclContext();
     do {
       StoredDeclsMap *Map = DC->getPrimaryContext()->LookupPtr;
       if (Map) {
         StoredDeclsMap::iterator Pos = Map->find(ND->getDeclName());
         assert(Pos != Map->end() && "no lookup entry for decl");
-        // Remove the decl only if it is contained.
-        StoredDeclsList::DeclsTy *Vec = Pos->second.getAsVector();
-        if ((Vec && is_contained(*Vec, ND)) || Pos->second.getAsDecl() == ND)
-          Pos->second.remove(ND);
       }
     } while (DC->isTransparentContext() && (DC = DC->getParent()));
   }
 }
 
 void DeclContext::addHiddenDecl(Decl *D) {
   assert(D->getLexicalDeclContext() == this &&
          "Decl inserted into wrong lexical context");
for (auto *D : DCtx->noload_decls()) {
     // or inline namespace, add the members of this declaration of that
     // context (recursively).
     if (auto *InnerCtx = dyn_cast<DeclContext>(D))
       if (InnerCtx->isTransparentContext() || InnerCtx->isInlineNamespace())
         buildLookupImpl(InnerCtx, Internal);
   }
 }
 
-NamedDecl *const DeclContextLookupResult::SingleElementDummyList = nullptr;
-
 DeclContext::lookup_result
 DeclContext::lookup(DeclarationName Name) const {
   assert(getDeclKind() != Decl::LinkageSpec &&
          getDeclKind() != Decl::Export &&
          "should not perform lookups into transparent contexts");
 
   const DeclContext *PrimaryContext = getPrimaryContext();
   if (PrimaryContext != this)
void DeclContext::makeDeclVisibleInContextImpl(NamedDecl *D, bool Internal) {
   // Insert this declaration into the map.
   StoredDeclsList &DeclNameEntries = (*Map)[D->getDeclName()];
 
   if (Internal) {
     // If this is being added as part of loading an external declaration,
     // this may not be the only external declaration with this name.
     // In this case, we never try to replace an existing declaration; we'll
     // handle that when we finalize the list of declarations for this name.
     DeclNameEntries.setHasExternalDecls();
-    DeclNameEntries.AddSubsequentDecl(D);
-    return;
-  }
-
-  if (DeclNameEntries.isNull()) {
-    DeclNameEntries.setOnlyValue(D);
-    return;
-  }
-
-  if (DeclNameEntries.HandleRedeclaration(D, /*IsKnownNewer*/!Internal)) {
-    // This declaration has replaced an existing one for which
-    // declarationReplaces returns true.
+    DeclNameEntries.prependDeclNoReplace(D);
     return;
   }
 
-  // Put this declaration into the appropriate slot.
-  DeclNameEntries.AddSubsequentDecl(D);
+  DeclNameEntries.addOrReplaceDecl(D);
 }
 
 UsingDirectiveDecl *DeclContext::udir_iterator::operator*() const {
   return cast<UsingDirectiveDecl>(*I);
 }
 
 /// Returns iterator range [First, Last) of UsingDirectiveDecls stored within
 /// this context.

clang/lib/AST/ExternalASTMerger.cpp

LookupSameContext(Source<TranslationUnitDecl *> SourceTU, const DeclContext *DC,
   auto SourceNameOrErr = ReverseImporter.Import(Name);
   if (!SourceNameOrErr) {
     llvm::consumeError(SourceNameOrErr.takeError());
     return nullptr;
   }
   Source<DeclarationName> SourceName = *SourceNameOrErr;
   DeclContext::lookup_result SearchResult =
       SourceParentDC.get()->lookup(SourceName.get());
-  size_t SearchResultSize = SearchResult.size();
-  if (SearchResultSize == 0 || SearchResultSize > 1) {
-    // There are two cases here.  First, we might not find the name.
-    // We might also find multiple copies, in which case we have no
-    // guarantee that the one we wanted is the one we pick.  (E.g.,
-    // if we have two specializations of the same template it is
-    // very hard to determine which is the one you want.)
-    //
-    // The Origins map fixes this problem by allowing the origin to be
-    // explicitly recorded, so we trigger that recording by returning
-    // nothing (rather than a possibly-inaccurate guess) here.
-    return nullptr;
-  } else {
-    NamedDecl *SearchResultDecl = SearchResult[0];
+
+  // There are two cases here. First, we might not find the name.
+  if (SearchResult.isSingleResult()) {
+    NamedDecl *SearchResultDecl = SearchResult.front();
     if (isa<DeclContext>(SearchResultDecl) &&
         SearchResultDecl->getKind() == DC->getDeclKind())
       return cast<DeclContext>(SearchResultDecl)->getPrimaryContext();
     return nullptr; // This type of lookup is unsupported
+  } else {
+    return nullptr;
   }
 }
 
 /// A custom implementation of ASTImporter, for ExternalASTMerger's purposes.
 ///
 /// There are several modifications:
 ///
 /// - It enables lazy lookup (via the HasExternalLexicalStorage flag and a few

clang/lib/AST/TypePrinter.cpp

void TypePrinter::AppendScope(DeclContext *DC, raw_ostream &OS,
 
   if (const auto *NS = dyn_cast<NamespaceDecl>(DC)) {
     if (Policy.SuppressUnwrittenScope && NS->isAnonymousNamespace())
       return AppendScope(DC->getParent(), OS, NameInScope);
 
     // Only suppress an inline namespace if the name has the same lookup
     // results in the enclosing namespace.
     if (Policy.SuppressInlineNamespace && NS->isInline() && NameInScope &&
-        DC->getParent()->lookup(NameInScope).size() ==
-            DC->lookup(NameInScope).size())
+        NS->isRedundantInlineQualifierFor(NameInScope))
       return AppendScope(DC->getParent(), OS, NameInScope);
 
     AppendScope(DC->getParent(), OS, NS->getDeclName());
     if (NS->getIdentifier())
       OS << NS->getName() << "::";
     else
       OS << "(anonymous namespace)::";
   } else if (const auto *Spec = dyn_cast<ClassTemplateSpecializationDecl>(DC)) {

clang/lib/CodeGen/CodeGenFunction.h

public:
   /// array size modifier, emit the object size divided by the size of \p EltTy.
   /// Otherwise return null.
   llvm::Value *LoadPassedObjectSize(const Expr *E, QualType EltTy);
 
   void EmitSanitizerStatReport(llvm::SanitizerStatKind SSK);
 
   struct MultiVersionResolverOption {
     llvm::Function *Function;
-    FunctionDecl *FD;
     struct Conds {
       StringRef Architecture;
       llvm::SmallVector<StringRef, 8> Features;
 
       Conds(StringRef Arch, ArrayRef<StringRef> Feats)
           : Architecture(Arch), Features(Feats.begin(), Feats.end()) {}
     } Conditions;
 

clang/lib/Sema/MultiplexExternalSemaSource.cpp

 //===--- MultiplexExternalSemaSource.cpp  ---------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the event dispatching to the subscribed clients.
 //
 //===----------------------------------------------------------------------===//
 #include "clang/Sema/MultiplexExternalSemaSource.h"
-#include "clang/AST/DeclContextInternals.h"
 #include "clang/Sema/Lookup.h"
 
 using namespace clang;
 
 char MultiplexExternalSemaSource::ID;
 
 ///Constructs a new multiplexing external sema source and appends the
 /// given element to it.

clang/lib/Sema/SemaDeclCXX.cpp

 }
 
 ValueDecl *Sema::tryLookupCtorInitMemberDecl(CXXRecordDecl *ClassDecl,
                                              CXXScopeSpec &SS,
                                              ParsedType TemplateTypeTy,
                                              IdentifierInfo *MemberOrBase) {
   if (SS.getScopeRep() || TemplateTypeTy)
     return nullptr;
-  DeclContext::lookup_result Result = ClassDecl->lookup(MemberOrBase);
-  if (Result.empty())
-    return nullptr;
-  ValueDecl *Member;
-  if ((Member = dyn_cast<FieldDecl>(Result.front())) ||
-      (Member = dyn_cast<IndirectFieldDecl>(Result.front())))
-    return Member;
+  for (auto *D : ClassDecl->lookup(MemberOrBase))
+    if (isa<FieldDecl>(D) || isa<IndirectFieldDecl>(D))
+      return cast<ValueDecl>(D);
   return nullptr;
 }
 
 /// Handle a C++ member initializer.
 MemInitResult
 Sema::BuildMemInitializer(Decl *ConstructorD,
                           Scope *S,
                           CXXScopeSpec &SS,
bool operator()(const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
     RecordDecl *BaseRecord =
         Specifier->getType()->castAs<RecordType>()->getDecl();
 
     DeclarationName Name = Method->getDeclName();
     assert(Name.getNameKind() == DeclarationName::Identifier);
 
     bool foundSameNameMethod = false;
     SmallVector<CXXMethodDecl *, 8> overloadedMethods;
-    for (Path.Decls = BaseRecord->lookup(Name); !Path.Decls.empty();
-         Path.Decls = Path.Decls.slice(1)) {
-      NamedDecl *D = Path.Decls.front();
+    for (Path.Decls = BaseRecord->lookup(Name).begin();
+         Path.Decls != DeclContext::lookup_iterator(); ++Path.Decls) {
+      NamedDecl *D = *Path.Decls;
       if (CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) {
         MD = MD->getCanonicalDecl();
         foundSameNameMethod = true;
         // Interested only in hidden virtual methods.
         if (!MD->isVirtual())
           continue;
         // If the method we are checking overrides a method from its base
         // don't warn about the other overloaded methods. Clang deviates from
ExprResult Sema::BuildCXXDefaultInitExpr(SourceLocation Loc, FieldDecl *Field) {
   // 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());
 
     FieldDecl *Pattern = nullptr;
     for (auto L : Lookup) {
       if (isa<FieldDecl>(L)) {
         Pattern = cast<FieldDecl>(L);
         break;
       }
     }
     assert(Pattern && "We must have set the Pattern!");
 
     if (!Pattern->hasInClassInitializer() ||
         InstantiateInClassInitializer(Loc, Field, Pattern,
                                       getTemplateInstantiationArgs(Field))) {
       // Don't diagnose this again.
       Field->setInvalidDecl();

clang/lib/Sema/SemaLookup.cpp

else if (N > 1 || HasFunctionTemplate)
     ResultKind = LookupResult::FoundOverloaded;
   else
     ResultKind = LookupResult::Found;
 }
 
 void LookupResult::addDeclsFromBasePaths(const CXXBasePaths &P) {
   CXXBasePaths::const_paths_iterator I, E;
   for (I = P.begin(), E = P.end(); I != E; ++I)
-    for (DeclContext::lookup_iterator DI = I->Decls.begin(),
-         DE = I->Decls.end(); DI != DE; ++DI)
+    for (DeclContext::lookup_iterator DI = I->Decls, DE = DI.end(); DI != DE;
+         ++DI)
       addDecl(*DI);
 }
 
 void LookupResult::setAmbiguousBaseSubobjects(CXXBasePaths &P) {
   Paths = new CXXBasePaths;
   Paths->swap(P);
   addDeclsFromBasePaths(*Paths);
   resolveKind();
bool Sema::LookupQualifiedName(LookupResult &R, DeclContext *LookupCtx,
   unsigned IDNS = R.getIdentifierNamespace();
 
   // Look for this member in our base classes.
   auto BaseCallback = [Name, IDNS](const CXXBaseSpecifier *Specifier,
                                    CXXBasePath &Path) -> bool {
     CXXRecordDecl *BaseRecord = Specifier->getType()->getAsCXXRecordDecl();
     // Drop leading non-matching lookup results from the declaration list so
     // we don't need to consider them again below.
-    for (Path.Decls = BaseRecord->lookup(Name); !Path.Decls.empty();
-         Path.Decls = Path.Decls.slice(1)) {
-      if (Path.Decls.front()->isInIdentifierNamespace(IDNS))
+    for (Path.Decls = BaseRecord->lookup(Name).begin();
+         Path.Decls != Path.Decls.end(); ++Path.Decls) {
+      if ((*Path.Decls)->isInIdentifierNamespace(IDNS))
         return true;
     }
     return false;
   };
 
   CXXBasePaths Paths;
   Paths.setOrigin(LookupRec);
   if (!LookupRec->lookupInBases(BaseCallback, Paths))
     return false;
 
   R.setNamingClass(LookupRec);
 
   // C++ [class.member.lookup]p2:
   //   [...] If the resulting set of declarations are not all from
   //   sub-objects of the same type, or the set has a nonstatic member
   //   and includes members from distinct sub-objects, there is an
   //   ambiguity and the program is ill-formed. Otherwise that set is
   //   the result of the lookup.
   QualType SubobjectType;
   int SubobjectNumber = 0;
   AccessSpecifier SubobjectAccess = AS_none;
 
   // Check whether the given lookup result contains only static members.
-  auto HasOnlyStaticMembers = [&](DeclContextLookupResult Result) {
-    for (NamedDecl *ND : Result)
-      if (ND->isInIdentifierNamespace(IDNS) && ND->isCXXInstanceMember())
+  auto HasOnlyStaticMembers = [&](DeclContext::lookup_iterator Result) {
+    for (DeclContext::lookup_iterator I = Result, E = I.end(); I != E; ++I)
+      if ((*I)->isInIdentifierNamespace(IDNS) && (*I)->isCXXInstanceMember())
         return false;
     return true;
   };
 
   bool TemplateNameLookup = R.isTemplateNameLookup();
 
   // Determine whether two sets of members contain the same members, as
   // required by C++ [class.member.lookup]p6.
-  auto HasSameDeclarations = [&](DeclContextLookupResult A,
-                                 DeclContextLookupResult B) {
+  auto HasSameDeclarations = [&](DeclContext::lookup_iterator A,
+                                 DeclContext::lookup_iterator B) {
     using Iterator = DeclContextLookupResult::iterator;
     using Result = const void *;
 
     auto Next = [&](Iterator &It, Iterator End) -> Result {
       while (It != End) {
         NamedDecl *ND = *It++;
         if (!ND->isInIdentifierNamespace(IDNS))
           continue;
auto Next = [&](Iterator &It, Iterator End) -> Result {
 
         return ND->getUnderlyingDecl()->getCanonicalDecl();
       }
       return nullptr;
     };
 
     // We'll often find the declarations are in the same order. Handle this
     // case (and the special case of only one declaration) efficiently.
-    Iterator AIt = A.begin(), BIt = B.begin(), AEnd = A.end(), BEnd = B.end();
+    Iterator AIt = A, BIt = B, AEnd, BEnd;
     while (true) {
       Result AResult = Next(AIt, AEnd);
       Result BResult = Next(BIt, BEnd);
       if (!AResult && !BResult)
         return true;
       if (!AResult || !BResult)
         return false;
       if (AResult != BResult) {
if (SubobjectNumber != PathElement.SubobjectNumber) {
       // subobjects. Name lookup is ambiguous.
       R.setAmbiguousBaseSubobjects(Paths);
       return true;
     }
   }
 
   // Lookup in a base class succeeded; return these results.
 
-  for (auto *D : Paths.front().Decls) {
+  for (DeclContext::lookup_iterator I = Paths.front().Decls, E = I.end();
+       I != E; ++I) {
     AccessSpecifier AS = CXXRecordDecl::MergeAccess(SubobjectAccess,
-                                                    D->getAccess());
-    if (NamedDecl *ND = R.getAcceptableDecl(D))
+                                                    (*I)->getAccess());
+    if (NamedDecl *ND = R.getAcceptableDecl(*I))
       R.addDecl(ND, AS);
   }
   R.resolveKind();
   return true;
 }
 
 /// Performs qualified name lookup or special type of lookup for
 /// "__super::" scope specifier.
void Sema::DiagnoseAmbiguousLookup(LookupResult &Result) {
   switch (Result.getAmbiguityKind()) {
   case LookupResult::AmbiguousBaseSubobjects: {
     CXXBasePaths *Paths = Result.getBasePaths();
     QualType SubobjectType = Paths->front().back().Base->getType();
     Diag(NameLoc, diag::err_ambiguous_member_multiple_subobjects)
       << Name << SubobjectType << getAmbiguousPathsDisplayString(*Paths)
       << LookupRange;
 
-    DeclContext::lookup_iterator Found = Paths->front().Decls.begin();
+    DeclContext::lookup_iterator Found = Paths->front().Decls;
     while (isa<CXXMethodDecl>(*Found) &&
            cast<CXXMethodDecl>(*Found)->isStatic())
       ++Found;
 
     Diag((*Found)->getLocation(), diag::note_ambiguous_member_found);
     break;
   }
 
   case LookupResult::AmbiguousBaseSubobjectTypes: {
     Diag(NameLoc, diag::err_ambiguous_member_multiple_subobject_types)
       << Name << LookupRange;
 
     CXXBasePaths *Paths = Result.getBasePaths();
     std::set<const NamedDecl *> DeclsPrinted;
     for (CXXBasePaths::paths_iterator Path = Paths->begin(),
                                       PathEnd = Paths->end();
          Path != PathEnd; ++Path) {
-      const NamedDecl *D = Path->Decls.front();
+      const NamedDecl *D = *Path->Decls;
       if (!D->isInIdentifierNamespace(Result.getIdentifierNamespace()))
         continue;
       if (DeclsPrinted.insert(D).second) {
         if (const auto *TD = dyn_cast<TypedefNameDecl>(D->getUnderlyingDecl()))
           Diag(D->getLocation(), diag::note_ambiguous_member_type_found)
               << TD->getUnderlyingType();
         else if (const auto *TD = dyn_cast<TypeDecl>(D->getUnderlyingDecl()))
           Diag(D->getLocation(), diag::note_ambiguous_member_type_found)

clang/lib/Sema/SemaObjCProperty.cpp

 static void
 CheckPropertyAgainstProtocol(Sema &S, ObjCPropertyDecl *Prop,
                              ObjCProtocolDecl *Proto,
                              llvm::SmallPtrSetImpl<ObjCProtocolDecl *> &Known) {
   // Have we seen this protocol before?
   if (!Known.insert(Proto).second)
     return;
 
   // Look for a property with the same name.
-  DeclContext::lookup_result R = Proto->lookup(Prop->getDeclName());
-  for (unsigned I = 0, N = R.size(); I != N; ++I) {
-    if (ObjCPropertyDecl *ProtoProp = dyn_cast<ObjCPropertyDecl>(R[I])) {
-      S.DiagnosePropertyMismatch(Prop, ProtoProp, Proto->getIdentifier(), true);
-      return;
-    }
-  }
+  if (ObjCPropertyDecl *ProtoProp =
+      Proto->lookup(Prop->getDeclName()).find_first<ObjCPropertyDecl>()) {
 
   // Check this property against any protocols we inherit.
   for (auto *P : Proto->protocols())
     CheckPropertyAgainstProtocol(S, Prop, P, Known);
 }
 
 static unsigned deducePropertyOwnershipFromType(Sema &S, QualType T) {
   // In GC mode, just look for the __weak qualifier.
Decl *Sema::ActOnProperty(Scope *S, SourceLocation AtLoc,
   if (Res->getType().getObjCLifetime())
     checkPropertyDeclWithOwnership(*this, Res);
 
   llvm::SmallPtrSet<ObjCProtocolDecl *, 16> KnownProtos;
   if (ObjCInterfaceDecl *IFace = dyn_cast<ObjCInterfaceDecl>(ClassDecl)) {
     // For a class, compare the property against a property in our superclass.
     bool FoundInSuper = false;
     ObjCInterfaceDecl *CurrentInterfaceDecl = IFace;
     while (ObjCInterfaceDecl *Super = CurrentInterfaceDecl->getSuperClass()) {
-      DeclContext::lookup_result R = Super->lookup(Res->getDeclName());
-      for (unsigned I = 0, N = R.size(); I != N; ++I) {
-        if (ObjCPropertyDecl *SuperProp = dyn_cast<ObjCPropertyDecl>(R[I])) {
-          DiagnosePropertyMismatch(Res, SuperProp, Super->getIdentifier(), false);
-          FoundInSuper = true;
-          break;
-        }
-      }
-      if (FoundInSuper)
-        break;
-      else
-        CurrentInterfaceDecl = Super;
+      if (ObjCPropertyDecl *SuperProp =
+          Super->lookup(Res->getDeclName()).find_first<ObjCPropertyDecl>()) {
     }
 
     if (FoundInSuper) {
       // Also compare the property against a property in our protocols.
       for (auto *P : CurrentInterfaceDecl->protocols()) {
         CheckPropertyAgainstProtocol(*this, Res, P, KnownProtos);
       }
     } else {
if (const ObjCCategoryDecl *CD =
       }
     }
     if (Synthesize && (PIkind & ObjCPropertyAttribute::kind_readonly) &&
         property->hasAttr<IBOutletAttr>() && !AtLoc.isValid()) {
       bool ReadWriteProperty = false;
       // Search into the class extensions and see if 'readonly property is
       // redeclared 'readwrite', then no warning is to be issued.
       for (auto *Ext : IDecl->known_extensions()) {
         DeclContext::lookup_result R = Ext->lookup(property->getDeclName());
-        if (!R.empty())
-          if (ObjCPropertyDecl *ExtProp = dyn_cast<ObjCPropertyDecl>(R[0])) {
-            PIkind = ExtProp->getPropertyAttributesAsWritten();
-            if (PIkind & ObjCPropertyAttribute::kind_readwrite) {
-              ReadWriteProperty = true;
-              break;
-            }
-          }
+        if (auto *ExtProp = R.find_first<ObjCPropertyDecl>()) {
       }
 
       if (!ReadWriteProperty) {
         Diag(property->getLocation(), diag::warn_auto_readonly_iboutlet_property)
             << property;
         SourceLocation readonlyLoc;
         if (LocPropertyAttribute(Context, "readonly",
                                  property->getLParenLoc(), readonlyLoc)) {

clang/lib/Sema/SemaTemplateInstantiate.cpp

if (auto *Function = dyn_cast<FunctionDecl>(D)) {
         MSInfo->setPointOfInstantiation(PointOfInstantiation);
       }
     } else if (auto *Field = dyn_cast<FieldDecl>(D)) {
       // No need to instantiate in-class initializers during explicit
       // instantiation.
       if (Field->hasInClassInitializer() && TSK == TSK_ImplicitInstantiation) {
         CXXRecordDecl *ClassPattern =
             Instantiation->getTemplateInstantiationPattern();
         DeclContext::lookup_result Lookup =
             ClassPattern->lookup(Field->getDeclName());
-        FieldDecl *Pattern = cast<FieldDecl>(Lookup.front());
+        FieldDecl *Pattern = Lookup.find_first<FieldDecl>();
+        assert(Pattern);
         InstantiateInClassInitializer(PointOfInstantiation, Field, Pattern,
                                       TemplateArgs);
       }
     }
   }
 }
 
 /// Instantiate the definitions of all of the members of the

clang/lib/Serialization/ASTReader.cpp

ASTReader::FindExternalVisibleDeclsByName(const DeclContext *DC,
   auto It = Lookups.find(DC);
   if (It == Lookups.end())
     return false;
 
   Deserializing LookupResults(this);
 
   // Load the list of declarations.
   SmallVector<NamedDecl *, 64> Decls;
+  llvm::SmallPtrSet<NamedDecl *, 8> Found;
   for (DeclID ID : It->second.Table.find(Name)) {
     NamedDecl *ND = cast<NamedDecl>(GetDecl(ID));
-    if (ND->getDeclName() == Name)
+    if (ND->getDeclName() == Name && Found.insert(ND).second)
       Decls.push_back(ND);
   }
 
   ++NumVisibleDeclContextsRead;
   SetExternalVisibleDeclsForName(DC, Name, Decls);
   return !Decls.empty();
 }
 

clang/lib/Serialization/ASTWriterDecl.cpp

 //===--- ASTWriterDecl.cpp - Declaration Serialization --------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file implements serialization for Declarations.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ASTCommon.h"
 #include "clang/AST/Attr.h"
 #include "clang/AST/DeclCXX.h"
-#include "clang/AST/DeclContextInternals.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/DeclVisitor.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/OpenMPClause.h"
 #include "clang/AST/PrettyDeclStackTrace.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Serialization/ASTReader.h"
 #include "clang/Serialization/ASTRecordWriter.h"

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

void StdLibraryFunctionsChecker::initFunctionSummaries(
 
   public:
     LookupType(const ASTContext &ACtx) : ACtx(ACtx) {}
 
     // Find the type. If not found then the optional is not set.
     llvm::Optional<QualType> operator()(StringRef Name) {
       IdentifierInfo &II = ACtx.Idents.get(Name);
       auto LookupRes = ACtx.getTranslationUnitDecl()->lookup(&II);
-      if (LookupRes.size() == 0)
+      if (LookupRes.empty())
         return None;
 
       // Prioritze typedef declarations.
       // This is needed in case of C struct typedefs. E.g.:
       //   typedef struct FILE FILE;
       // In this case, we have a RecordDecl 'struct FILE' with the name 'FILE'
       // and we have a TypedefDecl with the name 'FILE'.
       for (Decl *D : LookupRes)
struct AddToFunctionSummaryMap {
     // to the found FunctionDecl only if the signatures match.
     //
     // Returns true if the summary has been added, false otherwise.
     bool operator()(StringRef Name, Signature Sign, Summary Sum) {
       if (Sign.isInvalid())
         return false;
       IdentifierInfo &II = ACtx.Idents.get(Name);
       auto LookupRes = ACtx.getTranslationUnitDecl()->lookup(&II);
-      if (LookupRes.size() == 0)
+      if (LookupRes.empty())
         return false;
       for (Decl *D : LookupRes) {
         if (auto *FD = dyn_cast<FunctionDecl>(D)) {
           if (Sum.matchesAndSet(Sign, FD)) {
             auto Res = Map.insert({FD->getCanonicalDecl(), Sum});
             assert(Res.second && "Function already has a summary set!");
             (void)Res;
             if (DisplayLoadedSummaries) {

clang/test/PCH/cxx-explicit-specifier.cpp

+// RUN: %clang_cc1 -std=c++2a -include %s %s -ast-print -verify | FileCheck %s
+//
 // RUN: %clang_cc1 -std=c++2a -emit-pch %s -o %t-cxx2a
-// RUN: %clang_cc1 -std=c++2a -DUSE_PCH -include-pch %t-cxx2a %s -ast-print -verify | FileCheck %s
+// RUN: %clang_cc1 -std=c++2a -include-pch %t-cxx2a %s -ast-print -verify | FileCheck %s
 
 // RUN: %clang_cc1 -std=c++2a -emit-pch -fpch-instantiate-templates %s -o %t-cxx2a
-// RUN: %clang_cc1 -std=c++2a -DUSE_PCH -include-pch %t-cxx2a %s -ast-print -verify | FileCheck %s
+// RUN: %clang_cc1 -std=c++2a -include-pch %t-cxx2a %s -ast-print -verify | FileCheck %s
 
 #ifndef USE_PCH
 namespace inheriting_constructor {
   struct S {};
 
   template<typename X, typename Y> struct T {
     template<typename A>
     explicit((Y{}, true)) T(A &&a) {}

 //CHECK: explicit(false){{ +}}A(
 
 A a = { 0.0 }; //expected-error {{explicit deduction guide}}
 A a1 = { 0 };
 
 #endif
 
 }
+
+#define USE_PCH

clang/tools/libclang/CXType.cpp

const RecordDecl *RD =
         dyn_cast_or_null<RecordDecl>(cxcursor::getCursorDecl(PC));
   // verified in validateFieldParentType
   RD = RD->getDefinition();
   RecordDecl::lookup_result Res = RD->lookup(FieldName);
   // If a field of the parent record is incomplete, lookup will fail.
   // and we would return InvalidFieldName instead of Incomplete.
   // But this erroneous results does protects again a hidden assertion failure
   // in the RecordLayoutBuilder
-  if (Res.size() != 1)
+  if (!Res.isSingleResult())
     return CXTypeLayoutError_InvalidFieldName;
   if (const FieldDecl *FD = dyn_cast<FieldDecl>(Res.front()))
     return Ctx.getFieldOffset(FD);
   if (const IndirectFieldDecl *IFD = dyn_cast<IndirectFieldDecl>(Res.front()))
     return Ctx.getFieldOffset(IFD);
   // we don't want any other Decl Type.
   return CXTypeLayoutError_InvalidFieldName;
 }

clang/unittests/AST/ASTImporterTest.cpp

TranslationUnitDecl *FromTU =
       getTuDecl("struct X { friend void f(); };", Lang_CXX03, "input0.cc");
   auto *FromD = FirstDeclMatcher<FunctionDecl>().match(FromTU, FunctionPattern);
   ASSERT_TRUE(FromD->isInIdentifierNamespace(Decl::IDNS_OrdinaryFriend));
   ASSERT_FALSE(FromD->isInIdentifierNamespace(Decl::IDNS_Ordinary));
   {
     auto FromName = FromD->getDeclName();
     auto *Class = FirstDeclMatcher<CXXRecordDecl>().match(FromTU, ClassPattern);
     auto LookupRes = Class->noload_lookup(FromName);
-    ASSERT_EQ(LookupRes.size(), 0u);
+    ASSERT_TRUE(LookupRes.empty());
     LookupRes = FromTU->noload_lookup(FromName);
-    ASSERT_EQ(LookupRes.size(), 1u);
+    ASSERT_TRUE(LookupRes.isSingleResult());
   }
 
   auto *ToD = cast<FunctionDecl>(Import(FromD, Lang_CXX03));
   auto ToName = ToD->getDeclName();
 
   TranslationUnitDecl *ToTU = ToAST->getASTContext().getTranslationUnitDecl();
   auto *Class = FirstDeclMatcher<CXXRecordDecl>().match(ToTU, ClassPattern);
   auto LookupRes = Class->noload_lookup(ToName);
-  EXPECT_EQ(LookupRes.size(), 0u);
+  EXPECT_TRUE(LookupRes.empty());
   LookupRes = ToTU->noload_lookup(ToName);
-  EXPECT_EQ(LookupRes.size(), 1u);
+  EXPECT_TRUE(LookupRes.isSingleResult());
 
   EXPECT_EQ(DeclCounter<FunctionDecl>().match(ToTU, FunctionPattern), 1u);
   auto *To0 = FirstDeclMatcher<FunctionDecl>().match(ToTU, FunctionPattern);
   EXPECT_TRUE(To0->isInIdentifierNamespace(Decl::IDNS_OrdinaryFriend));
   EXPECT_FALSE(To0->isInIdentifierNamespace(Decl::IDNS_Ordinary));
 }
 
 TEST_P(ImportFriendFunctions, LookupWithProtoAfter) {
TEST_P(ImportFriendFunctions, LookupWithProtoAfter) {
   ASSERT_FALSE(FromFriend->isInIdentifierNamespace(Decl::IDNS_Ordinary));
   ASSERT_FALSE(FromNormal->isInIdentifierNamespace(Decl::IDNS_OrdinaryFriend));
   ASSERT_TRUE(FromNormal->isInIdentifierNamespace(Decl::IDNS_Ordinary));
 
   auto FromName = FromFriend->getDeclName();
   auto *FromClass =
       FirstDeclMatcher<CXXRecordDecl>().match(FromTU, ClassPattern);
   auto LookupRes = FromClass->noload_lookup(FromName);
-  ASSERT_EQ(LookupRes.size(), 0u);
+  ASSERT_TRUE(LookupRes.empty());
   LookupRes = FromTU->noload_lookup(FromName);
-  ASSERT_EQ(LookupRes.size(), 1u);
+  ASSERT_TRUE(LookupRes.isSingleResult());
 
   auto *ToFriend = cast<FunctionDecl>(Import(FromFriend, Lang_CXX03));
   auto ToName = ToFriend->getDeclName();
 
   TranslationUnitDecl *ToTU = ToAST->getASTContext().getTranslationUnitDecl();
   auto *ToClass = FirstDeclMatcher<CXXRecordDecl>().match(ToTU, ClassPattern);
   LookupRes = ToClass->noload_lookup(ToName);
-  EXPECT_EQ(LookupRes.size(), 0u);
+  EXPECT_TRUE(LookupRes.empty());
   LookupRes = ToTU->noload_lookup(ToName);
   // Test is disabled because this result is 2.
-  EXPECT_EQ(LookupRes.size(), 1u);
+  EXPECT_TRUE(LookupRes.isSingleResult());
 
   ASSERT_EQ(DeclCounter<FunctionDecl>().match(ToTU, FunctionPattern), 2u);
   ToFriend = FirstDeclMatcher<FunctionDecl>().match(ToTU, FunctionPattern);
   auto *ToNormal = LastDeclMatcher<FunctionDecl>().match(ToTU, FunctionPattern);
   EXPECT_TRUE(ToFriend->isInIdentifierNamespace(Decl::IDNS_OrdinaryFriend));
   EXPECT_FALSE(ToFriend->isInIdentifierNamespace(Decl::IDNS_Ordinary));
   EXPECT_FALSE(ToNormal->isInIdentifierNamespace(Decl::IDNS_OrdinaryFriend));
   EXPECT_TRUE(ToNormal->isInIdentifierNamespace(Decl::IDNS_Ordinary));
TEST_P(ImportFriendFunctions, LookupWithProtoBefore) {
   ASSERT_TRUE(FromNormal->isInIdentifierNamespace(Decl::IDNS_Ordinary));
   ASSERT_TRUE(FromFriend->isInIdentifierNamespace(Decl::IDNS_OrdinaryFriend));
   ASSERT_TRUE(FromFriend->isInIdentifierNamespace(Decl::IDNS_Ordinary));
 
   auto FromName = FromNormal->getDeclName();
   auto *FromClass =
       FirstDeclMatcher<CXXRecordDecl>().match(FromTU, ClassPattern);
   auto LookupRes = FromClass->noload_lookup(FromName);
-  ASSERT_EQ(LookupRes.size(), 0u);
+  ASSERT_TRUE(LookupRes.empty());
   LookupRes = FromTU->noload_lookup(FromName);
-  ASSERT_EQ(LookupRes.size(), 1u);
+  ASSERT_TRUE(LookupRes.isSingleResult());
 
   auto *ToNormal = cast<FunctionDecl>(Import(FromNormal, Lang_CXX03));
   auto ToName = ToNormal->getDeclName();
   TranslationUnitDecl *ToTU = ToAST->getASTContext().getTranslationUnitDecl();
 
   auto *ToClass = FirstDeclMatcher<CXXRecordDecl>().match(ToTU, ClassPattern);
   LookupRes = ToClass->noload_lookup(ToName);
-  EXPECT_EQ(LookupRes.size(), 0u);
+  EXPECT_TRUE(LookupRes.empty());
   LookupRes = ToTU->noload_lookup(ToName);
-  EXPECT_EQ(LookupRes.size(), 1u);
+  EXPECT_TRUE(LookupRes.isSingleResult());
 
   EXPECT_EQ(DeclCounter<FunctionDecl>().match(ToTU, FunctionPattern), 2u);
   ToNormal = FirstDeclMatcher<FunctionDecl>().match(ToTU, FunctionPattern);
   auto *ToFriend = LastDeclMatcher<FunctionDecl>().match(ToTU, FunctionPattern);
   EXPECT_FALSE(ToNormal->isInIdentifierNamespace(Decl::IDNS_OrdinaryFriend));
   EXPECT_TRUE(ToNormal->isInIdentifierNamespace(Decl::IDNS_Ordinary));
   EXPECT_TRUE(ToFriend->isInIdentifierNamespace(Decl::IDNS_OrdinaryFriend));
   EXPECT_TRUE(ToFriend->isInIdentifierNamespace(Decl::IDNS_Ordinary));
TEST_P(ImportFriendFunctions, ImportFriendChangesLookup) {
   auto FromNormalName = FromNormalF->getDeclName();
   auto FromFriendName = FromFriendF->getDeclName();
 
   ASSERT_TRUE(FromNormalF->isInIdentifierNamespace(Decl::IDNS_Ordinary));
   ASSERT_FALSE(FromNormalF->isInIdentifierNamespace(Decl::IDNS_OrdinaryFriend));
   ASSERT_FALSE(FromFriendF->isInIdentifierNamespace(Decl::IDNS_Ordinary));
   ASSERT_TRUE(FromFriendF->isInIdentifierNamespace(Decl::IDNS_OrdinaryFriend));
   auto LookupRes = FromNormalTU->noload_lookup(FromNormalName);
-  ASSERT_EQ(LookupRes.size(), 1u);
+  ASSERT_TRUE(LookupRes.isSingleResult());
   LookupRes = FromFriendTU->noload_lookup(FromFriendName);
-  ASSERT_EQ(LookupRes.size(), 1u);
+  ASSERT_TRUE(LookupRes.isSingleResult());
 
   auto *ToNormalF = cast<FunctionDecl>(Import(FromNormalF, Lang_CXX03));
   TranslationUnitDecl *ToTU = ToAST->getASTContext().getTranslationUnitDecl();
   auto ToName = ToNormalF->getDeclName();
   EXPECT_TRUE(ToNormalF->isInIdentifierNamespace(Decl::IDNS_Ordinary));
   EXPECT_FALSE(ToNormalF->isInIdentifierNamespace(Decl::IDNS_OrdinaryFriend));
   LookupRes = ToTU->noload_lookup(ToName);
-  EXPECT_EQ(LookupRes.size(), 1u);
+  EXPECT_TRUE(LookupRes.isSingleResult());
   EXPECT_EQ(DeclCounter<FunctionDecl>().match(ToTU, Pattern), 1u);
 
   auto *ToFriendF = cast<FunctionDecl>(Import(FromFriendF, Lang_CXX03));
   LookupRes = ToTU->noload_lookup(ToName);
-  EXPECT_EQ(LookupRes.size(), 1u);
+  EXPECT_TRUE(LookupRes.isSingleResult());
   EXPECT_EQ(DeclCounter<FunctionDecl>().match(ToTU, Pattern), 2u);
 
   EXPECT_TRUE(ToNormalF->isInIdentifierNamespace(Decl::IDNS_Ordinary));
   EXPECT_FALSE(ToNormalF->isInIdentifierNamespace(Decl::IDNS_OrdinaryFriend));
 
   EXPECT_TRUE(ToFriendF->isInIdentifierNamespace(Decl::IDNS_Ordinary));
   EXPECT_TRUE(ToFriendF->isInIdentifierNamespace(Decl::IDNS_OrdinaryFriend));
 }
TEST_P(DeclContextTest,
   ASSERT_NE(I, Map->end());
   StoredDeclsList &L = I->second;
   // The lookup table contains the most recent decl of A.
   ASSERT_NE(L.getAsDecl(), A0);
   ASSERT_EQ(L.getAsDecl(), A1);
 
   ASSERT_TRUE(L.getAsDecl());
   // Simulate the private function DeclContext::reconcileExternalVisibleStorage.
-  // The point here is to have a Vec with only one element, which is not the
-  // one we are going to delete from the DC later.
+  // We do not have a list with one element.
   L.setHasExternalDecls();
-  ASSERT_TRUE(L.getAsVector());
-  ASSERT_EQ(1u, L.getAsVector()->size());
+  ASSERT_FALSE(L.getAsList());
+  auto Results = L.getLookupResult();
+  ASSERT_EQ(1u, std::distance(Results.begin(), Results.end()));
 
   // This asserts in the old implementation.
   DC->removeDecl(A0);
   EXPECT_FALSE(DC->containsDecl(A0));
 }
 
 struct ImportFunctionTemplateSpecializations
     : ASTImporterOptionSpecificTestBase {};

lldb/source/Plugins/LanguageRuntime/ObjC/AppleObjCRuntime/AppleObjCDeclVendor.cpp

do {
           const_cast<clang::ObjCInterfaceDecl *>(interface_decl);
 
       if (!m_decl_vendor.FinishDecl(non_const_interface_decl))
         break;
 
       clang::DeclContext::lookup_result result =
           non_const_interface_decl->lookup(name);
 
-      return (result.size() != 0);
+      return (!result.empty());
     } while (false);
 
     SetNoExternalVisibleDeclsForName(decl_ctx, name);
     return false;
   }
 
   void CompleteType(clang::TagDecl *tag_decl) override {
 
do {
     clang::DeclarationName decl_name =
         ast_ctx.DeclarationNames.getIdentifier(&identifier_info);
 
     clang::DeclContext::lookup_result lookup_result =
         ast_ctx.getTranslationUnitDecl()->lookup(decl_name);
 
     if (!lookup_result.empty()) {
       if (clang::ObjCInterfaceDecl *result_iface_decl =
-              llvm::dyn_cast<clang::ObjCInterfaceDecl>(lookup_result[0])) {
+             llvm::dyn_cast<clang::ObjCInterfaceDecl>(*lookup_result.begin())) {
         if (log) {
           clang::QualType result_iface_type =
               ast_ctx.getObjCInterfaceType(result_iface_decl);
 
           uint64_t isa_value = LLDB_INVALID_ADDRESS;
           ClangASTMetadata *metadata = m_ast_ctx.GetMetadata(result_iface_decl);
           if (metadata)
             isa_value = metadata->GetISAPtr();

lldb/source/Plugins/SymbolFile/PDB/PDBASTParser.cpp

GetDeclFromContextByName(const clang::ASTContext &ast,
                          const clang::DeclContext &decl_context,
                          llvm::StringRef name) {
   clang::IdentifierInfo &ident = ast.Idents.get(name);
   clang::DeclarationName decl_name = ast.DeclarationNames.getIdentifier(&ident);
   clang::DeclContext::lookup_result result = decl_context.lookup(decl_name);
   if (result.empty())
     return nullptr;
 
-  return result[0];
+  return *result.begin();
 }
 
 static bool IsAnonymousNamespaceName(llvm::StringRef name) {
   return name == "`anonymous namespace'" || name == "`anonymous-namespace'";
 }
 
 static clang::CallingConv TranslateCallingConvention(PDB_CallingConv pdb_cc) {
   switch (pdb_cc) {

lldb/source/Plugins/TypeSystem/Clang/TypeSystemClang.h

if (type_name.GetLength()) {
 
       clang::IdentifierInfo &myIdent = ast.Idents.get(type_name.GetCString());
       clang::DeclarationName myName =
           ast.DeclarationNames.getIdentifier(&myIdent);
 
       clang::DeclContext::lookup_result result = decl_context->lookup(myName);
 
       if (!result.empty()) {
-        clang::NamedDecl *named_decl = result[0];
+        clang::NamedDecl *named_decl = *result.begin();
         if (const RecordDeclType *record_decl =
                 llvm::dyn_cast<RecordDeclType>(named_decl))
           compiler_type.SetCompilerType(
               this, clang::QualType(record_decl->getTypeForDecl(), 0)
                         .getAsOpaquePtr());
       }
     }
 

lldb/source/Plugins/TypeSystem/Clang/TypeSystemClang.cpp

auto find_overridden_methods =
 
           clang::DeclarationName name = decl->getDeclName();
 
           // If this is a destructor, check whether the base class destructor is
           // virtual.
           if (name.getNameKind() == clang::DeclarationName::CXXDestructorName)
             if (auto *baseDtorDecl = base_record->getDestructor()) {
               if (baseDtorDecl->isVirtual()) {
-                path.Decls = baseDtorDecl;
                 decls.push_back(baseDtorDecl);
                 return true;
               } else
                 return false;
             }
 
           // Otherwise, search for name in the base class.
-          for (path.Decls = base_record->lookup(name); !path.Decls.empty();
-               path.Decls = path.Decls.slice(1)) {
+          for (path.Decls = base_record->lookup(name).begin();
+               path.Decls != path.Decls.end(); ++path.Decls) {
             if (auto *method_decl =
-                    llvm::dyn_cast<clang::CXXMethodDecl>(path.Decls.front()))
+                    llvm::dyn_cast<clang::CXXMethodDecl>(*path.Decls))
               if (method_decl->isVirtual() && !isOverload(decl, method_decl)) {
-                path.Decls = method_decl;
                 decls.push_back(method_decl);
                 return true;
               }
           }
         }
 
         return false;
       };
case clang::Type::Record:
           clang::IdentifierInfo &ident_ref =
               getASTContext().Idents.get(name_sref);
           clang::DeclarationName decl_name(&ident_ref);
 
           clang::CXXBasePaths paths;
           if (cxx_record_decl->lookupInBases(
                   [decl_name](const clang::CXXBaseSpecifier *specifier,
                               clang::CXXBasePath &path) {
-                    path.Decls =
-                        specifier->getType()->getAsCXXRecordDecl()->lookup(
-                            decl_name);
-                    return !path.Decls.empty();
+                    CXXRecordDecl *record =
+                      specifier->getType()->getAsCXXRecordDecl();
+                    auto r = record->lookup(decl_name);
+                    path.Decls = r.begin();
+                    return !r.empty();
                   },
                   paths)) {
             clang::CXXBasePaths::const_paths_iterator path,
                 path_end = paths.end();
             for (path = paths.begin(); path != path_end; ++path) {
               const size_t num_path_elements = path->size();
               for (size_t e = 0; e < num_path_elements; ++e) {
                 clang::CXXBasePathElement elem = (*path)[e];
 
                 child_idx = GetIndexForRecordBase(parent_record_decl, elem.Base,
                                                   omit_empty_base_classes);
                 if (child_idx == UINT32_MAX) {
                   child_indexes.clear();
                   return 0;
                 } else {
                   child_indexes.push_back(child_idx);
                   parent_record_decl = llvm::cast<clang::RecordDecl>(
                       elem.Base->getType()
                           ->getAs<clang::RecordType>()
                           ->getDecl());
                 }
               }
-              for (clang::NamedDecl *path_decl : path->Decls) {
+              for (clang::DeclContext::lookup_iterator I = path->Decls, E;
+                   I != E; ++I) {
                 child_idx = GetIndexForRecordChild(
-                    parent_record_decl, path_decl, omit_empty_base_classes);
+                    parent_record_decl, *I, omit_empty_base_classes);
                 if (child_idx == UINT32_MAX) {
                   child_indexes.clear();
                   return 0;
                 } else {
                   child_indexes.push_back(child_idx);
                 }
               }
             }