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

1380–1385

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;

177–188

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

14111

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

clang/lib/Sema/SemaObjCProperty.cpp

1150–1151

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

clang/lib/Sema/SemaTemplateInstantiate.cpp

3415–3423

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

[v.g.vassilev]

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

[rsmith]

clang/include/clang/AST/DeclBase.h

1238–1241

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

1268–1274

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

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

1304–1313

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

1304–1335

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

1306

This should be allocated on the ASTContext's allocator.

1372

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

How about moving this to a function such as:

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

... used as (for example):

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

clang/include/clang/AST/DeclContextInternals.h

87–95

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

100

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

113

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

120

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

182

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

clang/lib/AST/DeclBase.cpp

1547–1551

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

1943–1946

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

clang/lib/AST/ExternalASTMerger.cpp

74–82

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

[v.g.vassilev]

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

[v.g.vassilev]

Minor typos, conciseness..

[v.g.vassilev]

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

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

[rsmith]

clang/include/clang/AST/ASTContext.h

654 ↗

(On Diff #314270)

Should we clear out Alloc->Rest here too?

clang/include/clang/AST/DeclBase.h

1226

1231

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

1256

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

1261–1262

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

1265–1268

Looks like this can be simplified a little.

1341–1342

This appears to be equivalent, and slightly simpler.

1344

Minor simplification, NFC.

1350

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.

74–77

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.

88–110

Maybe something like this.

107

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.

126–140

This can now be simplified.

145–146

I think this can be simplified too.

190–202

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

clang/lib/ARCMigrate/ObjCMT.cpp

652–654

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

clang/lib/AST/CXXInheritance.cpp

390 ↗

(On Diff #314270)

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

clang/lib/Sema/SemaObjCProperty.cpp

115–117

May as well use the shiny new toys :)

235–237

Can use find_first here too.

[v.g.vassilev]

Address most of the comments.

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

They are three kinds:

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

For a) we can adjust the test cases but

[v.g.vassilev]

clang/include/clang/AST/DeclBase.h

1261–1262

Indeed! That patch had too implementation versions already :)

clang/include/clang/AST/DeclContextInternals.h

88–110

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

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

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

clang/lib/Sema/SemaObjCProperty.cpp

115–117

Good catch, thanks!

[rsmith]

clang/include/clang/AST/DeclBase.h

1238

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

clang/include/clang/AST/DeclContextInternals.h

59–67

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.

88–110

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

1342

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

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

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

[v.g.vassilev]

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

[rsmith]

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

[v.g.vassilev]

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

clang/include/clang/AST/DeclBase.h

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;
 };
 
 /// 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 *>;
+  friend class StoredDeclsList;
+  struct ListNode;
+  /// When in collection form, this is what the Data pointer points to.
+  using Decls = llvm::PointerUnion<NamedDecl*, ListNode*>;
+  class ListNode {
+    friend class StoredDeclsList;
+    NamedDecl *D = nullptr;
+    Decls Rest = nullptr;
+  public:
+    ListNode(NamedDecl *ND) : D(ND) {}
+    bool empty() const {
+      assert((D || Rest.isNull()) && "D must be not nullptr if Rest is set.");
+      return !D && Rest.isNull();
+    }
 
-  ResultTy Result;
+    template<bool IsConst>
+    class ListNodeIterator {
+      friend class ListNode;
+      friend class DeclContextLookupResult;
+      using ConstIterator = ListNodeIterator<true>;
+    public:
+      using difference_type = ptrdiff_t;
+      using value_type =
+        typename std::conditional<IsConst, const NamedDecl*, NamedDecl*>::type;
+      using pointer = value_type *;
+      using reference = value_type &;
+      using iterator_category = std::forward_iterator_tag;
+    private:
+      Decls Ptr = nullptr;
+      ListNodeIterator(Decls Node) : Ptr(Node) { }
+      bool isNamedDecl() const { return Ptr.dyn_cast<NamedDecl*>(); }
+    public:
+      ListNodeIterator() = default;
+      // Converting ctor from non-const iterators to const iterators. SFINAE'd
+      // out for const iterator destinations so it doesn't end up as a user
+      // defined copy constructor.
+      template <bool IsConstSrc,
+                class = std::enable_if_t<!IsConstSrc && IsConst>>
+      ListNodeIterator(const ListNodeIterator<IsConstSrc> &I) : Ptr(I.Ptr) {}
 
-  // If there is only one lookup result, it would be invalidated by
-  // reallocations of the name table, so store it separately.
-  NamedDecl *Single = nullptr;
+      reference operator*() const {
+        assert(Ptr && "dereferencing end() iterator");
+        // FIXME: Remove the const_casts...
+        if (isNamedDecl())
+          return *(const_cast<NamedDecl**>(Ptr.getAddrOfPtr1()));
+        return Ptr.get<ListNode*>()->D;
+      }
+      pointer operator->() const {
+        assert(Ptr && "dereferencing end() iterator");
+        return isNamedDecl() ? Ptr.getAddrOfPtr1() : &Ptr.get<ListNode*>()->D;
+      }
+      bool operator==(const ConstIterator &X) const { return Ptr == X.Ptr; }
+      bool operator!=(const ConstIterator &X) const { return Ptr != X.Ptr; }
+      inline ListNodeIterator& operator++() { // ++It
+        assert(!Ptr.isNull() && "Advancing empty iterator");
+        assert((Ptr.dyn_cast<NamedDecl*>() || Ptr.dyn_cast<ListNode*>()) &&
+               "Advancing empty iterator");
 
-  static NamedDecl *const SingleElementDummyList;
+        Ptr = !isNamedDecl() ? Ptr.get<ListNode*>()->Rest : nullptr;
+        return *this;
+      }
+      ListNodeIterator operator++(int) { // It++
+        ListNodeIterator temp = *this;
+        ++(*this);
+        return temp;
+      }
+    };
+    using iterator = ListNodeIterator</*IsConst = */ false>;
+    using const_iterator = ListNodeIterator</*IsConst = */ true>;
 
-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 *>;
+    iterator begin() { return empty() ? end() : iterator(this); }
+    iterator end() { return iterator(); }
 
-  class iterator : public IteratorBase {
-    value_type SingleElement;
+    // const_iterator begin() { return empty() ? end() : const_iterator(this); }
+    // const_iterator end() const { return const_iterator(); }
 
-  public:
-    explicit iterator(pointer Pos, value_type Single = nullptr)
-        : IteratorBase(Pos), SingleElement(Single) {}
+    void push_back(NamedDecl *ND) {
+      assert(D && "No need to call push_back");
+      ListNode *Node = new ListNode(ND);
 
-    reference operator*() const {
-      return SingleElement ? SingleElement : IteratorBase::operator*();
+      ListNode *Prev = this;
+      while(Prev->Rest)
+        Prev = Prev->Rest.get<ListNode*>();
+
+      Prev->Rest = Node;
+    }
+
+    template<typename Pred>
+    void erase_if(Pred pred) {
+      ListNode *Prev = this;
+      if (D && Rest.isNull()) {
+        if (!pred(D))
+          D = nullptr;
+        return;
+      }
+
+      while(Prev && !pred(Prev->Rest.get<ListNode*>()->D))
+        Prev = Prev->Rest.get<ListNode*>();
+
+      assert(Prev && "list does not contain decl");
+      ListNode *ToDelete = Prev->Rest.get<ListNode*>();
+      Prev->Rest = ToDelete->Rest;
+      delete ToDelete;
+    }
+
+    void erase(NamedDecl *ND) {
+      erase_if([ND](NamedDecl *D){ return D == ND; });
     }
   };
 
+  Decls Result = nullptr;
+
+public:
+  DeclContextLookupResult() = default;
+  DeclContextLookupResult(Decls Result) : Result(Result) {}
+
+  using iterator = ListNode::ListNodeIterator</*IsConst = */ false>;
+  // FIXME: Add a proper const iterator
+  //using const_iterator = ListNode::ListNodeIterator</*IsConst = */ true>;
   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() {
+    if (empty())
+      return end();
+    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 {
+    if (Result.isNull())
+      return true;
+    // Might have been prepared to be filled later (see setHasExternalDecls).
+    if (Result.dyn_cast<NamedDecl*>() || !Result.get<ListNode*>()->empty())
+      return false;
+    return true;
+  }
+  bool isSingleResult() const {
+    return !empty() && Result.dyn_cast<NamedDecl*>();
+  }
+  bool equals(const DeclContextLookupResult &RHS) const {
+    if (empty() && RHS.empty())
+      return true;
+    if (empty() == RHS.empty())
+      return true;
+    if (isSingleResult() == RHS.isSingleResult())
+      return true;
 
-  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: We should probably copy, sort and compare one by one.
+    DeclContextLookupResult X = *this;
+    DeclContextLookupResult Y = RHS;
+    return std::distance(X.begin(), X.end()) ==
+      std::distance(Y.begin(), Y.end());
+  }
 
+  reference front() const { return *begin(); }
   // FIXME: Remove this from the interface
   DeclContextLookupResult slice(size_t N) const {
-    DeclContextLookupResult Sliced = Result.slice(N);
-    Sliced.Single = Single;
+    assert(N <= (size_t)std::distance(begin(), end()));
+    auto I = begin();
+    while(N--)
+      ++I;
+
+    DeclContextLookupResult Sliced(I.Ptr);
     return Sliced;
   }
 };
 
 /// 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):
 ///

clang/include/clang/AST/DeclContextInternals.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>;
+  using DeclsTy = DeclContextLookupResult::ListNode;
+  using Decls = DeclContextLookupResult::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
   /// external declarations.
-  llvm::PointerUnion<NamedDecl *, DeclsAndHasExternalTy> Data;
-
+  DeclsAndHasExternalTy Data;
 public:
   StoredDeclsList() = default;
 
   StoredDeclsList(StoredDeclsList &&RHS) : Data(RHS.Data) {
-    RHS.Data = (NamedDecl *)nullptr;
+    RHS.Data.setPointer(nullptr);
+    RHS.Data.setInt(0);
   }
 
   ~StoredDeclsList() {
     // If this is a vector-form, free the vector.
     if (DeclsTy *Vector = getAsVector())
-      delete Vector;
+      Vector->~DeclsTy();
   }
 
   StoredDeclsList &operator=(StoredDeclsList &&RHS) {
     if (DeclsTy *Vector = getAsVector())
       delete Vector;
     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 *>();
+    return getAsVectorAndHasExternal().getPointer().dyn_cast<NamedDecl *>();
   }
 
   DeclsAndHasExternalTy getAsVectorAndHasExternal() const {
-    return Data.dyn_cast<DeclsAndHasExternalTy>();
+    return Data;
   }
 
   DeclsTy *getAsVector() const {
-    return getAsVectorAndHasExternal().getPointer();
+    return getAsVectorAndHasExternal().getPointer().dyn_cast<DeclsTy*>();
   }
 
   bool hasExternalDecls() const {
     return getAsVectorAndHasExternal().getInt();
   }
 
   void setHasExternalDecls() {
     if (DeclsTy *Vec = getAsVector())
       Data = DeclsAndHasExternalTy(Vec, true);
     else {
-      DeclsTy *VT = new DeclsTy();
-      if (NamedDecl *OldD = getAsDecl())
-        VT->push_back(OldD);
+      if (NamedDecl *OldD = getAsDecl()) {
+        DeclsTy *VT = new DeclsTy(OldD);
         Data = DeclsAndHasExternalTy(VT, true);
       }
+      Data.setInt(1);
+    }
   }
 
   void setOnlyValue(NamedDecl *ND) {
     assert(!getAsVector() && "Not inline");
-    Data = ND;
+    Data.setPointer(ND);
     // Make sure that Data is a plain NamedDecl* so we can use its address
     // at getLookupResult.
-    assert(*(NamedDecl **)&Data == ND &&
+    assert(*(NamedDecl **)Data.getPointer().getAddrOfPtr1() == ND &&
            "PointerUnion mangles the NamedDecl pointer!");
   }
 
   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;
+      Data.setPointer(nullptr);
+      Data.setInt(0);
       return;
     }
 
     DeclsTy &Vec = *getAsVector();
-    DeclsTy::iterator I = llvm::find(Vec, D);
-    assert(I != Vec.end() && "list does not contain decl");
-    Vec.erase(I);
+    Vec.erase(D);
 
     assert(llvm::find(Vec, D) == Vec.end() && "list still contains decl");
   }
 
   /// 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());
+      Vec.erase_if([](NamedDecl *ND){ return ND->isFromASTFile(); });
+
       // Don't have any external decls any more.
+      if (Vec.empty())
+        Data = DeclsAndHasExternalTy((DeclsTy *) nullptr, false);
+      else
         Data = DeclsAndHasExternalTy(&Vec, false);
     }
   }
 
   /// getLookupResult - Return an array of all the decls that this list
   /// represents.
   DeclContext::lookup_result getLookupResult() {
-    if (isNull())
-      return DeclContext::lookup_result();
-
-    // If we have a single NamedDecl, return it.
-    if (NamedDecl *ND = getAsDecl()) {
-      assert(!isNull() && "Empty list isn't allowed");
-
-      // Data is a raw pointer to a NamedDecl*, return it.
-      return DeclContext::lookup_result(ND);
-    }
-
-    assert(getAsVector() && "Must have a vector at this point");
-    DeclsTy &Vector = *getAsVector();
-
-    // Otherwise, we have a range result.
-    return DeclContext::lookup_result(Vector);
+    return DeclContext::lookup_result(Data.getPointer());
   }
 
   /// 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))
bool HandleRedeclaration(NamedDecl *D, bool IsKnownNewer) {
     }
 
     return false;
   }
 
   /// 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");
 
     // 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);
+      DeclsTy *VT = new DeclsTy(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);
   }
 };
 
 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/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])) {
+      else if (auto *ClassProperty = dyn_cast<ObjCPropertyDecl>(R.front())) {
           if ((ClassProperty->getPropertyAttributes()
               != Property->getPropertyAttributes()) ||
               !Ctx.hasSameType(ClassProperty->getType(), Property->getType()))
             return false;
       }
       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 (auto I = R.begin(), E = R.end(); I != E; ++I)
+        if (ObjCMethodDecl *ImpMD = dyn_cast<ObjCMethodDecl>(*I))
           if (Ctx.ObjCMethodsAreEqual(MD, ImpMD)) {
             match = true;
             break;
           }
       if (!match)
         return false;
     }
   }
   return HasAtleastOneRequiredProperty || HasAtleastOneRequiredMethod;

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())
+        Ctx->lookup(NameInScope).equals(Ctx->getParent()->lookup(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

 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/ObjCRuntime.h"
 #include "clang/Basic/PartialDiagnostic.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/TargetInfo.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/VersionTuple.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
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)
+        if ((Vec && llvm::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) {
   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();
+    if (DeclNameEntries.isNull())
+      DeclNameEntries.setOnlyValue(D);
+    else
       DeclNameEntries.AddSubsequentDecl(D);
     return;
   }
 
   if (DeclNameEntries.isNull()) {
     DeclNameEntries.setOnlyValue(D);
     return;
   }
 

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.
+  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 {
+    // 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];
-    if (isa<DeclContext>(SearchResultDecl) &&
-        SearchResultDecl->getKind() == DC->getDeclKind())
-      return cast<DeclContext>(SearchResultDecl)->getPrimaryContext();
-    return nullptr; // This type of lookup is unsupported
   }
 }
 
 /// 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())
+        DC->getParent()->lookup(NameInScope).equals(DC->lookup(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/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,
if (Field->getType()->isReferenceType()) {
       Invalid = true;
       continue;
     }
 
     // Check for members of const-qualified, non-class type.
     QualType BaseType = Context.getBaseElementType(Field->getType());
     if (!BaseType->getAs<RecordType>() && BaseType.isConstQualified()) {
       Diag(ClassDecl->getLocation(), diag::err_uninitialized_member_for_assign)
         << Context.getTagDeclType(ClassDecl) << 1 << Field->getDeclName();

clang/lib/Sema/SemaObjCProperty.cpp

 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])) {
+  for (auto *R : Proto->lookup(Prop->getDeclName())) {
+    if (ObjCPropertyDecl *ProtoProp = dyn_cast<ObjCPropertyDecl>(R)) {
       S.DiagnosePropertyMismatch(Prop, ProtoProp, Proto->getIdentifier(), true);
       return;
     }
   }
 
   // Check this property against any protocols we inherit.
   for (auto *P : Proto->protocols())
     CheckPropertyAgainstProtocol(S, Prop, P, Known);
 }
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])) {
+      for (auto *R : Super->lookup(Res->getDeclName())) {
+        if (ObjCPropertyDecl *SuperProp = dyn_cast<ObjCPropertyDecl>(R)) {
           DiagnosePropertyMismatch(Res, SuperProp, Super->getIdentifier(), false);
           FoundInSuper = true;
           break;
         }
       }
       if (FoundInSuper)
         break;
       else
         CurrentInterfaceDecl = Super;
if ((IC = dyn_cast<ObjCImplementationDecl>(ClassImpDecl))) {
     }
     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])) {
+          if (auto *ExtProp = dyn_cast<ObjCPropertyDecl>(R.front())) {
             PIkind = ExtProp->getPropertyAttributesAsWritten();
             if (PIkind & ObjCPropertyAttribute::kind_readwrite) {
               ReadWriteProperty = true;
               break;
             }
           }
       }
 

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 = nullptr;
+        for (auto *R : Lookup)
+          if (isa<FieldDecl>(R)) {
+            Pattern = cast<FieldDecl>(R);
+            break;
+          }
+        assert(Pattern);
         InstantiateInClassInitializer(PointOfInstantiation, Field, Pattern,
                                       TemplateArgs);
       }
     }
   }
 }
 
 /// Instantiate the definitions of all of the members of the

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/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_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.
   L.setHasExternalDecls();
   ASSERT_TRUE(L.getAsVector());
-  ASSERT_EQ(1u, L.getAsVector()->size());
+  auto Results = L.getAsVector();
+  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 {};