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

1270–1275

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

[rsmith]

clang/include/clang/AST/DeclContextInternals.h

36

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

Instead, how about a representation such as:

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

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

190–235

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

15082–15093

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

clang/lib/Sema/SemaObjCProperty.cpp

1152–1153

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

clang/lib/Sema/SemaTemplateInstantiate.cpp

3415–3417

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.

1255–1261

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.

1290

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

1291–1300

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

1291–1322

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?

1293

This should be allocated on the ASTContext's allocator.

clang/include/clang/AST/DeclContextInternals.h

87–94

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

99

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

112

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

196

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

1546–1549

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–1944

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

76–84

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

This appears to be equivalent, and slightly simpler.

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?

1263

Minor simplification, NFC.

1265–1268

Looks like this can be simplified a little.

1267

clang/include/clang/AST/DeclContextInternals.h

37

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

76–79

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

90–112

Maybe something like this.

109

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–138

This can now be simplified.

144–159

I think this can be simplified too.

226–238

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

653–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

114–118

May as well use the shiny new toys :)

235–239

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

90–112

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–118

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

61–69

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

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

90–112

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

1260

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 = std::list<NamedDecl *>;
+  using ResultTy = ArrayRef<NamedDecl *>;
 
-  llvm::iterator_range<ResultTy::const_iterator> Result;
+  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 ResultTy const SingleElementDummyList;
+  static NamedDecl *const SingleElementDummyList;
 
 public:
-  DeclContextLookupResult()
-    : Result(llvm::make_range(SingleElementDummyList.end(),
-                              SingleElementDummyList.end())) {}
-  DeclContextLookupResult(const ResultTy &Result)
-    : Result(llvm::make_range(Result.begin(), Result.end())) {}
-
+  DeclContextLookupResult() = default;
+  DeclContextLookupResult(ArrayRef<NamedDecl *> Result)
+      : Result(Result) {}
   DeclContextLookupResult(NamedDecl *Single)
-    : Result(llvm::make_range(SingleElementDummyList.begin(),
-                              SingleElementDummyList.end())), Single(Single) {}
+      : Result(SingleElementDummyList), Single(Single) {}
 
   class iterator;
 
   using IteratorBase =
-    llvm::iterator_adaptor_base<iterator, ResultTy::const_iterator,
-                                std::forward_iterator_tag>;
+      llvm::iterator_adaptor_base<iterator, ResultTy::iterator,
+                                  std::random_access_iterator_tag, NamedDecl *>;
 
   class iterator : public IteratorBase {
     value_type SingleElement;
 
   public:
-    explicit iterator(ResultTy::const_iterator Pos, value_type Single = nullptr)
+    explicit iterator(pointer Pos, value_type Single = nullptr)
         : IteratorBase(Pos), SingleElement(Single) {}
 
     reference operator*() const {
       return SingleElement ? SingleElement : IteratorBase::operator*();
     }
   };
 
   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); }
 
   bool empty() const { return Result.empty(); }
-  size_t size() const {
-    if (empty())
-      return 0;
-    return Single ? 1 : std::distance(begin(), end());
-  };
-  reference front() const { return Single ? Single : *Result.begin(); }
-  reference back() const { return Single ? Single : *(--Result.end()); }
+  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 {
-    assert(size() >= N);
-    DeclContextLookupResult Sliced;
-    auto I = Result.begin();
-    std::advance(I, N);
-    Sliced.Result = llvm::make_range(I, Result.end());
+    DeclContextLookupResult Sliced = Result.slice(N);
     Sliced.Single = Single;
     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):
 ///
 ///   TranslationUnitDecl
 ///   ExternCContext
 ///   NamespaceDecl
 ///   TagDecl
 ///   OMPDeclareReductionDecl
 ///   OMPDeclareMapperDecl
 ///   FunctionDecl
 ///   ObjCMethodDecl
 ///   ObjCContainerDecl
 ///   LinkageSpecDecl
 ///   ExportDecl
 ///   BlockDecl
 ///   CapturedDecl
 class DeclContext {
   /// For makeDeclVisibleInContextImpl
   friend class ASTDeclReader;
   /// For reconcileExternalVisibleStorage, CreateStoredDeclsMap,
   /// hasNeedToReconcileExternalVisibleStorage
   friend class ExternalASTSource;
   /// For CreateStoredDeclsMap
   friend class DependentDiagnostic;
   /// For hasNeedToReconcileExternalVisibleStorage,
   /// hasLazyLocalLexicalLookups, hasLazyExternalLexicalLookups
   friend class ASTWriter;
 
   // We use uint64_t in the bit-fields below since some bit-fields
   // cross the unsigned boundary and this breaks the packing.
 
   /// Stores the bits used by DeclContext.
   /// If modified NumDeclContextBit, the ctor of DeclContext and the accessor
   /// methods in DeclContext should be updated appropriately.
   class DeclContextBitfields {
     friend class DeclContext;
     /// DeclKind - This indicates which class this is.
     uint64_t DeclKind : 7;
 
     /// Whether this declaration context also has some external
     /// storage that contains additional declarations that are lexically
     /// part of this context.
     mutable uint64_t ExternalLexicalStorage : 1;
 
     /// Whether this declaration context also has some external

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>
-#include <list>
 
 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 = std::list<NamedDecl *>;
+  using DeclsTy = SmallVector<NamedDecl *, 4>;
 
   /// A collection of declarations, with a flag to indicate if we have
   /// further external declarations.
   using DeclsAndHasExternalTy = llvm::PointerIntPair<DeclsTy *, 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;
 
 public:
   StoredDeclsList() = default;
 
   StoredDeclsList(StoredDeclsList &&RHS) : Data(RHS.Data) {
     RHS.Data = (NamedDecl *)nullptr;
   }
 
   ~StoredDeclsList() {
     // If this is a vector-form, free the vector.
     if (DeclsTy *Vector = getAsVector())
       delete Vector;
   }
 
   StoredDeclsList &operator=(StoredDeclsList &&RHS) {
     if (DeclsTy *Vector = getAsVector())
       delete Vector;
     Data = RHS.Data;
     RHS.Data = (NamedDecl *)nullptr;
     return *this;
   }
 
   bool isNull() const { return Data.isNull(); }
 
   NamedDecl *getAsDecl() const {
     return Data.dyn_cast<NamedDecl *>();
   }
 
   DeclsAndHasExternalTy getAsVectorAndHasExternal() const {
     return Data.dyn_cast<DeclsAndHasExternalTy>();
   }
 
   DeclsTy *getAsVector() const {
     return getAsVectorAndHasExternal().getPointer();
   }
 
   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);
       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!");
   }
 
   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;
     }
 
     DeclsTy &Vec = *getAsVector();
     DeclsTy::iterator I = llvm::find(Vec, D);
     assert(I != Vec.end() && "list does not contain decl");
     Vec.erase(I);
 
     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());
       // Don't have any external decls any more.
       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);
   }
 
   /// 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);
       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.push_back(I, D);
+      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;
 

clang/lib/ARCMigrate/ObjCMT.cpp

for (const auto *Property : PDecl->instance_properties()) {
         // 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 (auto *ClassProperty = dyn_cast<ObjCPropertyDecl>(R.front())) {
+      else if (ObjCPropertyDecl *ClassProperty = dyn_cast<ObjCPropertyDecl>(R[0])) {
           if ((ClassProperty->getPropertyAttributes()
               != Property->getPropertyAttributes()) ||
               !Ctx.hasSameType(ClassProperty->getType(), Property->getType()))
             return false;
       }
       else
         return false;
     }
for (const auto *MD : PDecl->methods()) {
       if (MD->getImplementationControl() == ObjCMethodDecl::Optional)
         continue;
       DeclContext::lookup_result R = ImpDecl->lookup(MD->getDeclName());
       if (R.size() == 0)
         return false;
       bool match = false;
       HasAtleastOneRequiredMethod = true;
       for (unsigned I = 0, N = R.size(); I != N; ++I)
-        if (ObjCMethodDecl *ImpMD = dyn_cast<ObjCMethodDecl>(R.front()))
+        if (ObjCMethodDecl *ImpMD = dyn_cast<ObjCMethodDecl>(R[0]))
           if (Ctx.ObjCMethodsAreEqual(MD, ImpMD)) {
             match = true;
             break;
           }
       if (!match)
         return false;
     }
   }
   return HasAtleastOneRequiredProperty || HasAtleastOneRequiredMethod;

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 && llvm::is_contained(*Vec, ND)) ||
-            Pos->second.getAsDecl() == ND)
+        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);
   }
 }
 
-DeclContextLookupResult::ResultTy
-const DeclContextLookupResult::SingleElementDummyList = { nullptr };
+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();
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();
     DeclNameEntries.AddSubsequentDecl(D);
     return;
   }
 
   if (DeclNameEntries.isNull()) {
     DeclNameEntries.setOnlyValue(D);
     return;
   }
 
   if (DeclNameEntries.HandleRedeclaration(D, /*IsKnownNewer*/!Internal)) {

clang/lib/AST/ExternalASTMerger.cpp

LookupSameContext(Source<TranslationUnitDecl *> SourceTU, const DeclContext *DC,
   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.front();
+    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/Sema/SemaDeclCXX.cpp

 }
 
 ValueDecl *Sema::tryLookupCtorInitMemberDecl(CXXRecordDecl *ClassDecl,
                                              CXXScopeSpec &SS,
                                              ParsedType TemplateTypeTy,
                                              IdentifierInfo *MemberOrBase) {
   if (SS.getScopeRep() || TemplateTypeTy)
     return nullptr;
-  for (auto *D : ClassDecl->lookup(MemberOrBase))
-    if (isa<FieldDecl>(D) || isa<IndirectFieldDecl>(D))
-      return cast<ValueDecl>(D);
+  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;
   return nullptr;
 }
 
 /// Handle a C++ member initializer.
 MemInitResult
 Sema::BuildMemInitializer(Decl *ConstructorD,
                           Scope *S,
                           CXXScopeSpec &SS,
if (isTemplateInstantiation(ParentRD->getTemplateSpecializationKind())) {
     DeclContext::lookup_result Lookup =
         ClassPattern->lookup(Field->getDeclName());
 
     // Lookup can return at most two results: the pattern for the field, or the
     // injected class name of the parent record. No other member can have the
     // same name as the field.
     // In modules mode, lookup can return multiple results (coming from
     // different modules).
     assert((getLangOpts().Modules || (!Lookup.empty() && Lookup.size() <= 2)) &&
            "more than two lookup results for field name");
-    FieldDecl *Pattern = dyn_cast<FieldDecl>(Lookup.back());
+    FieldDecl *Pattern = dyn_cast<FieldDecl>(Lookup[0]);
     if (!Pattern) {
-      assert(isa<CXXRecordDecl>(Lookup.back()) &&
+      assert(isa<CXXRecordDecl>(Lookup[0]) &&
              "cannot have other non-field member with same name");
       for (auto L : Lookup)
         if (isa<FieldDecl>(L)) {
           Pattern = cast<FieldDecl>(L);
           break;
         }
       assert(Pattern && "We must have set the Pattern!");
     }
 
     if (!Pattern->hasInClassInitializer() ||
         InstantiateInClassInitializer(Loc, Field, Pattern,
                                       getTemplateInstantiationArgs(Field))) {
       // Don't diagnose this again.
       Field->setInvalidDecl();
       return ExprError();

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.
-  for (auto *R : Proto->lookup(Prop->getDeclName())) {
-    if (ObjCPropertyDecl *ProtoProp = dyn_cast<ObjCPropertyDecl>(R)) {
+  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;
     }
   }
 
   // Check this property against any protocols we inherit.
   for (auto *P : Proto->protocols())
     CheckPropertyAgainstProtocol(S, Prop, P, Known);
 }
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()) {
-      for (auto *R : Super->lookup(Res->getDeclName())) {
-        if (ObjCPropertyDecl *SuperProp = dyn_cast<ObjCPropertyDecl>(R)) {
+      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 ((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 (auto *ExtProp = dyn_cast<ObjCPropertyDecl>(R.front())) {
+          if (ObjCPropertyDecl *ExtProp = dyn_cast<ObjCPropertyDecl>(R[0])) {
             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.back());
+        FieldDecl *Pattern = cast<FieldDecl>(Lookup.front());
         InstantiateInClassInitializer(PointOfInstantiation, Field, Pattern,
                                       TemplateArgs);
       }
     }
   }
 }
 
 /// Instantiate the definitions of all of the members of the