xref: /freebsd/contrib/llvm-project/clang/lib/Sema/SemaLookup.cpp (revision b1879975794772ee51f0b4865753364c7d7626c3)
1 //===--------------------- SemaLookup.cpp - Name Lookup  ------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 //  This file implements name lookup for C, C++, Objective-C, and
10 //  Objective-C++.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/AST/ASTContext.h"
15 #include "clang/AST/CXXInheritance.h"
16 #include "clang/AST/Decl.h"
17 #include "clang/AST/DeclCXX.h"
18 #include "clang/AST/DeclLookups.h"
19 #include "clang/AST/DeclObjC.h"
20 #include "clang/AST/DeclTemplate.h"
21 #include "clang/AST/Expr.h"
22 #include "clang/AST/ExprCXX.h"
23 #include "clang/Basic/Builtins.h"
24 #include "clang/Basic/FileManager.h"
25 #include "clang/Basic/LangOptions.h"
26 #include "clang/Lex/HeaderSearch.h"
27 #include "clang/Lex/ModuleLoader.h"
28 #include "clang/Lex/Preprocessor.h"
29 #include "clang/Sema/DeclSpec.h"
30 #include "clang/Sema/Lookup.h"
31 #include "clang/Sema/Overload.h"
32 #include "clang/Sema/RISCVIntrinsicManager.h"
33 #include "clang/Sema/Scope.h"
34 #include "clang/Sema/ScopeInfo.h"
35 #include "clang/Sema/Sema.h"
36 #include "clang/Sema/SemaInternal.h"
37 #include "clang/Sema/SemaRISCV.h"
38 #include "clang/Sema/TemplateDeduction.h"
39 #include "clang/Sema/TypoCorrection.h"
40 #include "llvm/ADT/STLExtras.h"
41 #include "llvm/ADT/STLForwardCompat.h"
42 #include "llvm/ADT/SmallPtrSet.h"
43 #include "llvm/ADT/TinyPtrVector.h"
44 #include "llvm/ADT/edit_distance.h"
45 #include "llvm/Support/Casting.h"
46 #include "llvm/Support/ErrorHandling.h"
47 #include <algorithm>
48 #include <iterator>
49 #include <list>
50 #include <optional>
51 #include <set>
52 #include <utility>
53 #include <vector>
54 
55 #include "OpenCLBuiltins.inc"
56 
57 using namespace clang;
58 using namespace sema;
59 
60 namespace {
61   class UnqualUsingEntry {
62     const DeclContext *Nominated;
63     const DeclContext *CommonAncestor;
64 
65   public:
66     UnqualUsingEntry(const DeclContext *Nominated,
67                      const DeclContext *CommonAncestor)
68       : Nominated(Nominated), CommonAncestor(CommonAncestor) {
69     }
70 
71     const DeclContext *getCommonAncestor() const {
72       return CommonAncestor;
73     }
74 
75     const DeclContext *getNominatedNamespace() const {
76       return Nominated;
77     }
78 
79     // Sort by the pointer value of the common ancestor.
80     struct Comparator {
81       bool operator()(const UnqualUsingEntry &L, const UnqualUsingEntry &R) {
82         return L.getCommonAncestor() < R.getCommonAncestor();
83       }
84 
85       bool operator()(const UnqualUsingEntry &E, const DeclContext *DC) {
86         return E.getCommonAncestor() < DC;
87       }
88 
89       bool operator()(const DeclContext *DC, const UnqualUsingEntry &E) {
90         return DC < E.getCommonAncestor();
91       }
92     };
93   };
94 
95   /// A collection of using directives, as used by C++ unqualified
96   /// lookup.
97   class UnqualUsingDirectiveSet {
98     Sema &SemaRef;
99 
100     typedef SmallVector<UnqualUsingEntry, 8> ListTy;
101 
102     ListTy list;
103     llvm::SmallPtrSet<DeclContext*, 8> visited;
104 
105   public:
106     UnqualUsingDirectiveSet(Sema &SemaRef) : SemaRef(SemaRef) {}
107 
108     void visitScopeChain(Scope *S, Scope *InnermostFileScope) {
109       // C++ [namespace.udir]p1:
110       //   During unqualified name lookup, the names appear as if they
111       //   were declared in the nearest enclosing namespace which contains
112       //   both the using-directive and the nominated namespace.
113       DeclContext *InnermostFileDC = InnermostFileScope->getEntity();
114       assert(InnermostFileDC && InnermostFileDC->isFileContext());
115 
116       for (; S; S = S->getParent()) {
117         // C++ [namespace.udir]p1:
118         //   A using-directive shall not appear in class scope, but may
119         //   appear in namespace scope or in block scope.
120         DeclContext *Ctx = S->getEntity();
121         if (Ctx && Ctx->isFileContext()) {
122           visit(Ctx, Ctx);
123         } else if (!Ctx || Ctx->isFunctionOrMethod()) {
124           for (auto *I : S->using_directives())
125             if (SemaRef.isVisible(I))
126               visit(I, InnermostFileDC);
127         }
128       }
129     }
130 
131     // Visits a context and collect all of its using directives
132     // recursively.  Treats all using directives as if they were
133     // declared in the context.
134     //
135     // A given context is only every visited once, so it is important
136     // that contexts be visited from the inside out in order to get
137     // the effective DCs right.
138     void visit(DeclContext *DC, DeclContext *EffectiveDC) {
139       if (!visited.insert(DC).second)
140         return;
141 
142       addUsingDirectives(DC, EffectiveDC);
143     }
144 
145     // Visits a using directive and collects all of its using
146     // directives recursively.  Treats all using directives as if they
147     // were declared in the effective DC.
148     void visit(UsingDirectiveDecl *UD, DeclContext *EffectiveDC) {
149       DeclContext *NS = UD->getNominatedNamespace();
150       if (!visited.insert(NS).second)
151         return;
152 
153       addUsingDirective(UD, EffectiveDC);
154       addUsingDirectives(NS, EffectiveDC);
155     }
156 
157     // Adds all the using directives in a context (and those nominated
158     // by its using directives, transitively) as if they appeared in
159     // the given effective context.
160     void addUsingDirectives(DeclContext *DC, DeclContext *EffectiveDC) {
161       SmallVector<DeclContext*, 4> queue;
162       while (true) {
163         for (auto *UD : DC->using_directives()) {
164           DeclContext *NS = UD->getNominatedNamespace();
165           if (SemaRef.isVisible(UD) && visited.insert(NS).second) {
166             addUsingDirective(UD, EffectiveDC);
167             queue.push_back(NS);
168           }
169         }
170 
171         if (queue.empty())
172           return;
173 
174         DC = queue.pop_back_val();
175       }
176     }
177 
178     // Add a using directive as if it had been declared in the given
179     // context.  This helps implement C++ [namespace.udir]p3:
180     //   The using-directive is transitive: if a scope contains a
181     //   using-directive that nominates a second namespace that itself
182     //   contains using-directives, the effect is as if the
183     //   using-directives from the second namespace also appeared in
184     //   the first.
185     void addUsingDirective(UsingDirectiveDecl *UD, DeclContext *EffectiveDC) {
186       // Find the common ancestor between the effective context and
187       // the nominated namespace.
188       DeclContext *Common = UD->getNominatedNamespace();
189       while (!Common->Encloses(EffectiveDC))
190         Common = Common->getParent();
191       Common = Common->getPrimaryContext();
192 
193       list.push_back(UnqualUsingEntry(UD->getNominatedNamespace(), Common));
194     }
195 
196     void done() { llvm::sort(list, UnqualUsingEntry::Comparator()); }
197 
198     typedef ListTy::const_iterator const_iterator;
199 
200     const_iterator begin() const { return list.begin(); }
201     const_iterator end() const { return list.end(); }
202 
203     llvm::iterator_range<const_iterator>
204     getNamespacesFor(const DeclContext *DC) const {
205       return llvm::make_range(std::equal_range(begin(), end(),
206                                                DC->getPrimaryContext(),
207                                                UnqualUsingEntry::Comparator()));
208     }
209   };
210 } // end anonymous namespace
211 
212 // Retrieve the set of identifier namespaces that correspond to a
213 // specific kind of name lookup.
214 static inline unsigned getIDNS(Sema::LookupNameKind NameKind,
215                                bool CPlusPlus,
216                                bool Redeclaration) {
217   unsigned IDNS = 0;
218   switch (NameKind) {
219   case Sema::LookupObjCImplicitSelfParam:
220   case Sema::LookupOrdinaryName:
221   case Sema::LookupRedeclarationWithLinkage:
222   case Sema::LookupLocalFriendName:
223   case Sema::LookupDestructorName:
224     IDNS = Decl::IDNS_Ordinary;
225     if (CPlusPlus) {
226       IDNS |= Decl::IDNS_Tag | Decl::IDNS_Member | Decl::IDNS_Namespace;
227       if (Redeclaration)
228         IDNS |= Decl::IDNS_TagFriend | Decl::IDNS_OrdinaryFriend;
229     }
230     if (Redeclaration)
231       IDNS |= Decl::IDNS_LocalExtern;
232     break;
233 
234   case Sema::LookupOperatorName:
235     // Operator lookup is its own crazy thing;  it is not the same
236     // as (e.g.) looking up an operator name for redeclaration.
237     assert(!Redeclaration && "cannot do redeclaration operator lookup");
238     IDNS = Decl::IDNS_NonMemberOperator;
239     break;
240 
241   case Sema::LookupTagName:
242     if (CPlusPlus) {
243       IDNS = Decl::IDNS_Type;
244 
245       // When looking for a redeclaration of a tag name, we add:
246       // 1) TagFriend to find undeclared friend decls
247       // 2) Namespace because they can't "overload" with tag decls.
248       // 3) Tag because it includes class templates, which can't
249       //    "overload" with tag decls.
250       if (Redeclaration)
251         IDNS |= Decl::IDNS_Tag | Decl::IDNS_TagFriend | Decl::IDNS_Namespace;
252     } else {
253       IDNS = Decl::IDNS_Tag;
254     }
255     break;
256 
257   case Sema::LookupLabel:
258     IDNS = Decl::IDNS_Label;
259     break;
260 
261   case Sema::LookupMemberName:
262     IDNS = Decl::IDNS_Member;
263     if (CPlusPlus)
264       IDNS |= Decl::IDNS_Tag | Decl::IDNS_Ordinary;
265     break;
266 
267   case Sema::LookupNestedNameSpecifierName:
268     IDNS = Decl::IDNS_Type | Decl::IDNS_Namespace;
269     break;
270 
271   case Sema::LookupNamespaceName:
272     IDNS = Decl::IDNS_Namespace;
273     break;
274 
275   case Sema::LookupUsingDeclName:
276     assert(Redeclaration && "should only be used for redecl lookup");
277     IDNS = Decl::IDNS_Ordinary | Decl::IDNS_Tag | Decl::IDNS_Member |
278            Decl::IDNS_Using | Decl::IDNS_TagFriend | Decl::IDNS_OrdinaryFriend |
279            Decl::IDNS_LocalExtern;
280     break;
281 
282   case Sema::LookupObjCProtocolName:
283     IDNS = Decl::IDNS_ObjCProtocol;
284     break;
285 
286   case Sema::LookupOMPReductionName:
287     IDNS = Decl::IDNS_OMPReduction;
288     break;
289 
290   case Sema::LookupOMPMapperName:
291     IDNS = Decl::IDNS_OMPMapper;
292     break;
293 
294   case Sema::LookupAnyName:
295     IDNS = Decl::IDNS_Ordinary | Decl::IDNS_Tag | Decl::IDNS_Member
296       | Decl::IDNS_Using | Decl::IDNS_Namespace | Decl::IDNS_ObjCProtocol
297       | Decl::IDNS_Type;
298     break;
299   }
300   return IDNS;
301 }
302 
303 void LookupResult::configure() {
304   IDNS = getIDNS(LookupKind, getSema().getLangOpts().CPlusPlus,
305                  isForRedeclaration());
306 
307   // If we're looking for one of the allocation or deallocation
308   // operators, make sure that the implicitly-declared new and delete
309   // operators can be found.
310   switch (NameInfo.getName().getCXXOverloadedOperator()) {
311   case OO_New:
312   case OO_Delete:
313   case OO_Array_New:
314   case OO_Array_Delete:
315     getSema().DeclareGlobalNewDelete();
316     break;
317 
318   default:
319     break;
320   }
321 
322   // Compiler builtins are always visible, regardless of where they end
323   // up being declared.
324   if (IdentifierInfo *Id = NameInfo.getName().getAsIdentifierInfo()) {
325     if (unsigned BuiltinID = Id->getBuiltinID()) {
326       if (!getSema().Context.BuiltinInfo.isPredefinedLibFunction(BuiltinID))
327         AllowHidden = true;
328     }
329   }
330 }
331 
332 bool LookupResult::checkDebugAssumptions() const {
333   // This function is never called by NDEBUG builds.
334   assert(ResultKind != NotFound || Decls.size() == 0);
335   assert(ResultKind != Found || Decls.size() == 1);
336   assert(ResultKind != FoundOverloaded || Decls.size() > 1 ||
337          (Decls.size() == 1 &&
338           isa<FunctionTemplateDecl>((*begin())->getUnderlyingDecl())));
339   assert(ResultKind != FoundUnresolvedValue || checkUnresolved());
340   assert(ResultKind != Ambiguous || Decls.size() > 1 ||
341          (Decls.size() == 1 && (Ambiguity == AmbiguousBaseSubobjects ||
342                                 Ambiguity == AmbiguousBaseSubobjectTypes)));
343   assert((Paths != nullptr) == (ResultKind == Ambiguous &&
344                                 (Ambiguity == AmbiguousBaseSubobjectTypes ||
345                                  Ambiguity == AmbiguousBaseSubobjects)));
346   return true;
347 }
348 
349 // Necessary because CXXBasePaths is not complete in Sema.h
350 void LookupResult::deletePaths(CXXBasePaths *Paths) {
351   delete Paths;
352 }
353 
354 /// Get a representative context for a declaration such that two declarations
355 /// will have the same context if they were found within the same scope.
356 static const DeclContext *getContextForScopeMatching(const Decl *D) {
357   // For function-local declarations, use that function as the context. This
358   // doesn't account for scopes within the function; the caller must deal with
359   // those.
360   if (const DeclContext *DC = D->getLexicalDeclContext();
361       DC->isFunctionOrMethod())
362     return DC;
363 
364   // Otherwise, look at the semantic context of the declaration. The
365   // declaration must have been found there.
366   return D->getDeclContext()->getRedeclContext();
367 }
368 
369 /// Determine whether \p D is a better lookup result than \p Existing,
370 /// given that they declare the same entity.
371 static bool isPreferredLookupResult(Sema &S, Sema::LookupNameKind Kind,
372                                     const NamedDecl *D,
373                                     const NamedDecl *Existing) {
374   // When looking up redeclarations of a using declaration, prefer a using
375   // shadow declaration over any other declaration of the same entity.
376   if (Kind == Sema::LookupUsingDeclName && isa<UsingShadowDecl>(D) &&
377       !isa<UsingShadowDecl>(Existing))
378     return true;
379 
380   const auto *DUnderlying = D->getUnderlyingDecl();
381   const auto *EUnderlying = Existing->getUnderlyingDecl();
382 
383   // If they have different underlying declarations, prefer a typedef over the
384   // original type (this happens when two type declarations denote the same
385   // type), per a generous reading of C++ [dcl.typedef]p3 and p4. The typedef
386   // might carry additional semantic information, such as an alignment override.
387   // However, per C++ [dcl.typedef]p5, when looking up a tag name, prefer a tag
388   // declaration over a typedef. Also prefer a tag over a typedef for
389   // destructor name lookup because in some contexts we only accept a
390   // class-name in a destructor declaration.
391   if (DUnderlying->getCanonicalDecl() != EUnderlying->getCanonicalDecl()) {
392     assert(isa<TypeDecl>(DUnderlying) && isa<TypeDecl>(EUnderlying));
393     bool HaveTag = isa<TagDecl>(EUnderlying);
394     bool WantTag =
395         Kind == Sema::LookupTagName || Kind == Sema::LookupDestructorName;
396     return HaveTag != WantTag;
397   }
398 
399   // Pick the function with more default arguments.
400   // FIXME: In the presence of ambiguous default arguments, we should keep both,
401   //        so we can diagnose the ambiguity if the default argument is needed.
402   //        See C++ [over.match.best]p3.
403   if (const auto *DFD = dyn_cast<FunctionDecl>(DUnderlying)) {
404     const auto *EFD = cast<FunctionDecl>(EUnderlying);
405     unsigned DMin = DFD->getMinRequiredArguments();
406     unsigned EMin = EFD->getMinRequiredArguments();
407     // If D has more default arguments, it is preferred.
408     if (DMin != EMin)
409       return DMin < EMin;
410     // FIXME: When we track visibility for default function arguments, check
411     // that we pick the declaration with more visible default arguments.
412   }
413 
414   // Pick the template with more default template arguments.
415   if (const auto *DTD = dyn_cast<TemplateDecl>(DUnderlying)) {
416     const auto *ETD = cast<TemplateDecl>(EUnderlying);
417     unsigned DMin = DTD->getTemplateParameters()->getMinRequiredArguments();
418     unsigned EMin = ETD->getTemplateParameters()->getMinRequiredArguments();
419     // If D has more default arguments, it is preferred. Note that default
420     // arguments (and their visibility) is monotonically increasing across the
421     // redeclaration chain, so this is a quick proxy for "is more recent".
422     if (DMin != EMin)
423       return DMin < EMin;
424     // If D has more *visible* default arguments, it is preferred. Note, an
425     // earlier default argument being visible does not imply that a later
426     // default argument is visible, so we can't just check the first one.
427     for (unsigned I = DMin, N = DTD->getTemplateParameters()->size();
428         I != N; ++I) {
429       if (!S.hasVisibleDefaultArgument(
430               ETD->getTemplateParameters()->getParam(I)) &&
431           S.hasVisibleDefaultArgument(
432               DTD->getTemplateParameters()->getParam(I)))
433         return true;
434     }
435   }
436 
437   // VarDecl can have incomplete array types, prefer the one with more complete
438   // array type.
439   if (const auto *DVD = dyn_cast<VarDecl>(DUnderlying)) {
440     const auto *EVD = cast<VarDecl>(EUnderlying);
441     if (EVD->getType()->isIncompleteType() &&
442         !DVD->getType()->isIncompleteType()) {
443       // Prefer the decl with a more complete type if visible.
444       return S.isVisible(DVD);
445     }
446     return false; // Avoid picking up a newer decl, just because it was newer.
447   }
448 
449   // For most kinds of declaration, it doesn't really matter which one we pick.
450   if (!isa<FunctionDecl>(DUnderlying) && !isa<VarDecl>(DUnderlying)) {
451     // If the existing declaration is hidden, prefer the new one. Otherwise,
452     // keep what we've got.
453     return !S.isVisible(Existing);
454   }
455 
456   // Pick the newer declaration; it might have a more precise type.
457   for (const Decl *Prev = DUnderlying->getPreviousDecl(); Prev;
458        Prev = Prev->getPreviousDecl())
459     if (Prev == EUnderlying)
460       return true;
461   return false;
462 }
463 
464 /// Determine whether \p D can hide a tag declaration.
465 static bool canHideTag(const NamedDecl *D) {
466   // C++ [basic.scope.declarative]p4:
467   //   Given a set of declarations in a single declarative region [...]
468   //   exactly one declaration shall declare a class name or enumeration name
469   //   that is not a typedef name and the other declarations shall all refer to
470   //   the same variable, non-static data member, or enumerator, or all refer
471   //   to functions and function templates; in this case the class name or
472   //   enumeration name is hidden.
473   // C++ [basic.scope.hiding]p2:
474   //   A class name or enumeration name can be hidden by the name of a
475   //   variable, data member, function, or enumerator declared in the same
476   //   scope.
477   // An UnresolvedUsingValueDecl always instantiates to one of these.
478   D = D->getUnderlyingDecl();
479   return isa<VarDecl>(D) || isa<EnumConstantDecl>(D) || isa<FunctionDecl>(D) ||
480          isa<FunctionTemplateDecl>(D) || isa<FieldDecl>(D) ||
481          isa<UnresolvedUsingValueDecl>(D);
482 }
483 
484 /// Resolves the result kind of this lookup.
485 void LookupResult::resolveKind() {
486   unsigned N = Decls.size();
487 
488   // Fast case: no possible ambiguity.
489   if (N == 0) {
490     assert(ResultKind == NotFound ||
491            ResultKind == NotFoundInCurrentInstantiation);
492     return;
493   }
494 
495   // If there's a single decl, we need to examine it to decide what
496   // kind of lookup this is.
497   if (N == 1) {
498     const NamedDecl *D = (*Decls.begin())->getUnderlyingDecl();
499     if (isa<FunctionTemplateDecl>(D))
500       ResultKind = FoundOverloaded;
501     else if (isa<UnresolvedUsingValueDecl>(D))
502       ResultKind = FoundUnresolvedValue;
503     return;
504   }
505 
506   // Don't do any extra resolution if we've already resolved as ambiguous.
507   if (ResultKind == Ambiguous) return;
508 
509   llvm::SmallDenseMap<const NamedDecl *, unsigned, 16> Unique;
510   llvm::SmallDenseMap<QualType, unsigned, 16> UniqueTypes;
511 
512   bool Ambiguous = false;
513   bool ReferenceToPlaceHolderVariable = false;
514   bool HasTag = false, HasFunction = false;
515   bool HasFunctionTemplate = false, HasUnresolved = false;
516   const NamedDecl *HasNonFunction = nullptr;
517 
518   llvm::SmallVector<const NamedDecl *, 4> EquivalentNonFunctions;
519   llvm::BitVector RemovedDecls(N);
520 
521   for (unsigned I = 0; I < N; I++) {
522     const NamedDecl *D = Decls[I]->getUnderlyingDecl();
523     D = cast<NamedDecl>(D->getCanonicalDecl());
524 
525     // Ignore an invalid declaration unless it's the only one left.
526     // Also ignore HLSLBufferDecl which not have name conflict with other Decls.
527     if ((D->isInvalidDecl() || isa<HLSLBufferDecl>(D)) &&
528         N - RemovedDecls.count() > 1) {
529       RemovedDecls.set(I);
530       continue;
531     }
532 
533     // C++ [basic.scope.hiding]p2:
534     //   A class name or enumeration name can be hidden by the name of
535     //   an object, function, or enumerator declared in the same
536     //   scope. If a class or enumeration name and an object, function,
537     //   or enumerator are declared in the same scope (in any order)
538     //   with the same name, the class or enumeration name is hidden
539     //   wherever the object, function, or enumerator name is visible.
540     if (HideTags && isa<TagDecl>(D)) {
541       bool Hidden = false;
542       for (auto *OtherDecl : Decls) {
543         if (canHideTag(OtherDecl) && !OtherDecl->isInvalidDecl() &&
544             getContextForScopeMatching(OtherDecl)->Equals(
545                 getContextForScopeMatching(Decls[I]))) {
546           RemovedDecls.set(I);
547           Hidden = true;
548           break;
549         }
550       }
551       if (Hidden)
552         continue;
553     }
554 
555     std::optional<unsigned> ExistingI;
556 
557     // Redeclarations of types via typedef can occur both within a scope
558     // and, through using declarations and directives, across scopes. There is
559     // no ambiguity if they all refer to the same type, so unique based on the
560     // canonical type.
561     if (const auto *TD = dyn_cast<TypeDecl>(D)) {
562       QualType T = getSema().Context.getTypeDeclType(TD);
563       auto UniqueResult = UniqueTypes.insert(
564           std::make_pair(getSema().Context.getCanonicalType(T), I));
565       if (!UniqueResult.second) {
566         // The type is not unique.
567         ExistingI = UniqueResult.first->second;
568       }
569     }
570 
571     // For non-type declarations, check for a prior lookup result naming this
572     // canonical declaration.
573     if (!ExistingI) {
574       auto UniqueResult = Unique.insert(std::make_pair(D, I));
575       if (!UniqueResult.second) {
576         // We've seen this entity before.
577         ExistingI = UniqueResult.first->second;
578       }
579     }
580 
581     if (ExistingI) {
582       // This is not a unique lookup result. Pick one of the results and
583       // discard the other.
584       if (isPreferredLookupResult(getSema(), getLookupKind(), Decls[I],
585                                   Decls[*ExistingI]))
586         Decls[*ExistingI] = Decls[I];
587       RemovedDecls.set(I);
588       continue;
589     }
590 
591     // Otherwise, do some decl type analysis and then continue.
592 
593     if (isa<UnresolvedUsingValueDecl>(D)) {
594       HasUnresolved = true;
595     } else if (isa<TagDecl>(D)) {
596       if (HasTag)
597         Ambiguous = true;
598       HasTag = true;
599     } else if (isa<FunctionTemplateDecl>(D)) {
600       HasFunction = true;
601       HasFunctionTemplate = true;
602     } else if (isa<FunctionDecl>(D)) {
603       HasFunction = true;
604     } else {
605       if (HasNonFunction) {
606         // If we're about to create an ambiguity between two declarations that
607         // are equivalent, but one is an internal linkage declaration from one
608         // module and the other is an internal linkage declaration from another
609         // module, just skip it.
610         if (getSema().isEquivalentInternalLinkageDeclaration(HasNonFunction,
611                                                              D)) {
612           EquivalentNonFunctions.push_back(D);
613           RemovedDecls.set(I);
614           continue;
615         }
616         if (D->isPlaceholderVar(getSema().getLangOpts()) &&
617             getContextForScopeMatching(D) ==
618                 getContextForScopeMatching(Decls[I])) {
619           ReferenceToPlaceHolderVariable = true;
620         }
621         Ambiguous = true;
622       }
623       HasNonFunction = D;
624     }
625   }
626 
627   // FIXME: This diagnostic should really be delayed until we're done with
628   // the lookup result, in case the ambiguity is resolved by the caller.
629   if (!EquivalentNonFunctions.empty() && !Ambiguous)
630     getSema().diagnoseEquivalentInternalLinkageDeclarations(
631         getNameLoc(), HasNonFunction, EquivalentNonFunctions);
632 
633   // Remove decls by replacing them with decls from the end (which
634   // means that we need to iterate from the end) and then truncating
635   // to the new size.
636   for (int I = RemovedDecls.find_last(); I >= 0; I = RemovedDecls.find_prev(I))
637     Decls[I] = Decls[--N];
638   Decls.truncate(N);
639 
640   if ((HasNonFunction && (HasFunction || HasUnresolved)) ||
641       (HideTags && HasTag && (HasFunction || HasNonFunction || HasUnresolved)))
642     Ambiguous = true;
643 
644   if (Ambiguous && ReferenceToPlaceHolderVariable)
645     setAmbiguous(LookupResult::AmbiguousReferenceToPlaceholderVariable);
646   else if (Ambiguous)
647     setAmbiguous(LookupResult::AmbiguousReference);
648   else if (HasUnresolved)
649     ResultKind = LookupResult::FoundUnresolvedValue;
650   else if (N > 1 || HasFunctionTemplate)
651     ResultKind = LookupResult::FoundOverloaded;
652   else
653     ResultKind = LookupResult::Found;
654 }
655 
656 void LookupResult::addDeclsFromBasePaths(const CXXBasePaths &P) {
657   CXXBasePaths::const_paths_iterator I, E;
658   for (I = P.begin(), E = P.end(); I != E; ++I)
659     for (DeclContext::lookup_iterator DI = I->Decls, DE = DI.end(); DI != DE;
660          ++DI)
661       addDecl(*DI);
662 }
663 
664 void LookupResult::setAmbiguousBaseSubobjects(CXXBasePaths &P) {
665   Paths = new CXXBasePaths;
666   Paths->swap(P);
667   addDeclsFromBasePaths(*Paths);
668   resolveKind();
669   setAmbiguous(AmbiguousBaseSubobjects);
670 }
671 
672 void LookupResult::setAmbiguousBaseSubobjectTypes(CXXBasePaths &P) {
673   Paths = new CXXBasePaths;
674   Paths->swap(P);
675   addDeclsFromBasePaths(*Paths);
676   resolveKind();
677   setAmbiguous(AmbiguousBaseSubobjectTypes);
678 }
679 
680 void LookupResult::print(raw_ostream &Out) {
681   Out << Decls.size() << " result(s)";
682   if (isAmbiguous()) Out << ", ambiguous";
683   if (Paths) Out << ", base paths present";
684 
685   for (iterator I = begin(), E = end(); I != E; ++I) {
686     Out << "\n";
687     (*I)->print(Out, 2);
688   }
689 }
690 
691 LLVM_DUMP_METHOD void LookupResult::dump() {
692   llvm::errs() << "lookup results for " << getLookupName().getAsString()
693                << ":\n";
694   for (NamedDecl *D : *this)
695     D->dump();
696 }
697 
698 /// Diagnose a missing builtin type.
699 static QualType diagOpenCLBuiltinTypeError(Sema &S, llvm::StringRef TypeClass,
700                                            llvm::StringRef Name) {
701   S.Diag(SourceLocation(), diag::err_opencl_type_not_found)
702       << TypeClass << Name;
703   return S.Context.VoidTy;
704 }
705 
706 /// Lookup an OpenCL enum type.
707 static QualType getOpenCLEnumType(Sema &S, llvm::StringRef Name) {
708   LookupResult Result(S, &S.Context.Idents.get(Name), SourceLocation(),
709                       Sema::LookupTagName);
710   S.LookupName(Result, S.TUScope);
711   if (Result.empty())
712     return diagOpenCLBuiltinTypeError(S, "enum", Name);
713   EnumDecl *Decl = Result.getAsSingle<EnumDecl>();
714   if (!Decl)
715     return diagOpenCLBuiltinTypeError(S, "enum", Name);
716   return S.Context.getEnumType(Decl);
717 }
718 
719 /// Lookup an OpenCL typedef type.
720 static QualType getOpenCLTypedefType(Sema &S, llvm::StringRef Name) {
721   LookupResult Result(S, &S.Context.Idents.get(Name), SourceLocation(),
722                       Sema::LookupOrdinaryName);
723   S.LookupName(Result, S.TUScope);
724   if (Result.empty())
725     return diagOpenCLBuiltinTypeError(S, "typedef", Name);
726   TypedefNameDecl *Decl = Result.getAsSingle<TypedefNameDecl>();
727   if (!Decl)
728     return diagOpenCLBuiltinTypeError(S, "typedef", Name);
729   return S.Context.getTypedefType(Decl);
730 }
731 
732 /// Get the QualType instances of the return type and arguments for an OpenCL
733 /// builtin function signature.
734 /// \param S (in) The Sema instance.
735 /// \param OpenCLBuiltin (in) The signature currently handled.
736 /// \param GenTypeMaxCnt (out) Maximum number of types contained in a generic
737 ///        type used as return type or as argument.
738 ///        Only meaningful for generic types, otherwise equals 1.
739 /// \param RetTypes (out) List of the possible return types.
740 /// \param ArgTypes (out) List of the possible argument types.  For each
741 ///        argument, ArgTypes contains QualTypes for the Cartesian product
742 ///        of (vector sizes) x (types) .
743 static void GetQualTypesForOpenCLBuiltin(
744     Sema &S, const OpenCLBuiltinStruct &OpenCLBuiltin, unsigned &GenTypeMaxCnt,
745     SmallVector<QualType, 1> &RetTypes,
746     SmallVector<SmallVector<QualType, 1>, 5> &ArgTypes) {
747   // Get the QualType instances of the return types.
748   unsigned Sig = SignatureTable[OpenCLBuiltin.SigTableIndex];
749   OCL2Qual(S, TypeTable[Sig], RetTypes);
750   GenTypeMaxCnt = RetTypes.size();
751 
752   // Get the QualType instances of the arguments.
753   // First type is the return type, skip it.
754   for (unsigned Index = 1; Index < OpenCLBuiltin.NumTypes; Index++) {
755     SmallVector<QualType, 1> Ty;
756     OCL2Qual(S, TypeTable[SignatureTable[OpenCLBuiltin.SigTableIndex + Index]],
757              Ty);
758     GenTypeMaxCnt = (Ty.size() > GenTypeMaxCnt) ? Ty.size() : GenTypeMaxCnt;
759     ArgTypes.push_back(std::move(Ty));
760   }
761 }
762 
763 /// Create a list of the candidate function overloads for an OpenCL builtin
764 /// function.
765 /// \param Context (in) The ASTContext instance.
766 /// \param GenTypeMaxCnt (in) Maximum number of types contained in a generic
767 ///        type used as return type or as argument.
768 ///        Only meaningful for generic types, otherwise equals 1.
769 /// \param FunctionList (out) List of FunctionTypes.
770 /// \param RetTypes (in) List of the possible return types.
771 /// \param ArgTypes (in) List of the possible types for the arguments.
772 static void GetOpenCLBuiltinFctOverloads(
773     ASTContext &Context, unsigned GenTypeMaxCnt,
774     std::vector<QualType> &FunctionList, SmallVector<QualType, 1> &RetTypes,
775     SmallVector<SmallVector<QualType, 1>, 5> &ArgTypes) {
776   FunctionProtoType::ExtProtoInfo PI(
777       Context.getDefaultCallingConvention(false, false, true));
778   PI.Variadic = false;
779 
780   // Do not attempt to create any FunctionTypes if there are no return types,
781   // which happens when a type belongs to a disabled extension.
782   if (RetTypes.size() == 0)
783     return;
784 
785   // Create FunctionTypes for each (gen)type.
786   for (unsigned IGenType = 0; IGenType < GenTypeMaxCnt; IGenType++) {
787     SmallVector<QualType, 5> ArgList;
788 
789     for (unsigned A = 0; A < ArgTypes.size(); A++) {
790       // Bail out if there is an argument that has no available types.
791       if (ArgTypes[A].size() == 0)
792         return;
793 
794       // Builtins such as "max" have an "sgentype" argument that represents
795       // the corresponding scalar type of a gentype.  The number of gentypes
796       // must be a multiple of the number of sgentypes.
797       assert(GenTypeMaxCnt % ArgTypes[A].size() == 0 &&
798              "argument type count not compatible with gentype type count");
799       unsigned Idx = IGenType % ArgTypes[A].size();
800       ArgList.push_back(ArgTypes[A][Idx]);
801     }
802 
803     FunctionList.push_back(Context.getFunctionType(
804         RetTypes[(RetTypes.size() != 1) ? IGenType : 0], ArgList, PI));
805   }
806 }
807 
808 /// When trying to resolve a function name, if isOpenCLBuiltin() returns a
809 /// non-null <Index, Len> pair, then the name is referencing an OpenCL
810 /// builtin function.  Add all candidate signatures to the LookUpResult.
811 ///
812 /// \param S (in) The Sema instance.
813 /// \param LR (inout) The LookupResult instance.
814 /// \param II (in) The identifier being resolved.
815 /// \param FctIndex (in) Starting index in the BuiltinTable.
816 /// \param Len (in) The signature list has Len elements.
817 static void InsertOCLBuiltinDeclarationsFromTable(Sema &S, LookupResult &LR,
818                                                   IdentifierInfo *II,
819                                                   const unsigned FctIndex,
820                                                   const unsigned Len) {
821   // The builtin function declaration uses generic types (gentype).
822   bool HasGenType = false;
823 
824   // Maximum number of types contained in a generic type used as return type or
825   // as argument.  Only meaningful for generic types, otherwise equals 1.
826   unsigned GenTypeMaxCnt;
827 
828   ASTContext &Context = S.Context;
829 
830   for (unsigned SignatureIndex = 0; SignatureIndex < Len; SignatureIndex++) {
831     const OpenCLBuiltinStruct &OpenCLBuiltin =
832         BuiltinTable[FctIndex + SignatureIndex];
833 
834     // Ignore this builtin function if it is not available in the currently
835     // selected language version.
836     if (!isOpenCLVersionContainedInMask(Context.getLangOpts(),
837                                         OpenCLBuiltin.Versions))
838       continue;
839 
840     // Ignore this builtin function if it carries an extension macro that is
841     // not defined. This indicates that the extension is not supported by the
842     // target, so the builtin function should not be available.
843     StringRef Extensions = FunctionExtensionTable[OpenCLBuiltin.Extension];
844     if (!Extensions.empty()) {
845       SmallVector<StringRef, 2> ExtVec;
846       Extensions.split(ExtVec, " ");
847       bool AllExtensionsDefined = true;
848       for (StringRef Ext : ExtVec) {
849         if (!S.getPreprocessor().isMacroDefined(Ext)) {
850           AllExtensionsDefined = false;
851           break;
852         }
853       }
854       if (!AllExtensionsDefined)
855         continue;
856     }
857 
858     SmallVector<QualType, 1> RetTypes;
859     SmallVector<SmallVector<QualType, 1>, 5> ArgTypes;
860 
861     // Obtain QualType lists for the function signature.
862     GetQualTypesForOpenCLBuiltin(S, OpenCLBuiltin, GenTypeMaxCnt, RetTypes,
863                                  ArgTypes);
864     if (GenTypeMaxCnt > 1) {
865       HasGenType = true;
866     }
867 
868     // Create function overload for each type combination.
869     std::vector<QualType> FunctionList;
870     GetOpenCLBuiltinFctOverloads(Context, GenTypeMaxCnt, FunctionList, RetTypes,
871                                  ArgTypes);
872 
873     SourceLocation Loc = LR.getNameLoc();
874     DeclContext *Parent = Context.getTranslationUnitDecl();
875     FunctionDecl *NewOpenCLBuiltin;
876 
877     for (const auto &FTy : FunctionList) {
878       NewOpenCLBuiltin = FunctionDecl::Create(
879           Context, Parent, Loc, Loc, II, FTy, /*TInfo=*/nullptr, SC_Extern,
880           S.getCurFPFeatures().isFPConstrained(), false,
881           FTy->isFunctionProtoType());
882       NewOpenCLBuiltin->setImplicit();
883 
884       // Create Decl objects for each parameter, adding them to the
885       // FunctionDecl.
886       const auto *FP = cast<FunctionProtoType>(FTy);
887       SmallVector<ParmVarDecl *, 4> ParmList;
888       for (unsigned IParm = 0, e = FP->getNumParams(); IParm != e; ++IParm) {
889         ParmVarDecl *Parm = ParmVarDecl::Create(
890             Context, NewOpenCLBuiltin, SourceLocation(), SourceLocation(),
891             nullptr, FP->getParamType(IParm), nullptr, SC_None, nullptr);
892         Parm->setScopeInfo(0, IParm);
893         ParmList.push_back(Parm);
894       }
895       NewOpenCLBuiltin->setParams(ParmList);
896 
897       // Add function attributes.
898       if (OpenCLBuiltin.IsPure)
899         NewOpenCLBuiltin->addAttr(PureAttr::CreateImplicit(Context));
900       if (OpenCLBuiltin.IsConst)
901         NewOpenCLBuiltin->addAttr(ConstAttr::CreateImplicit(Context));
902       if (OpenCLBuiltin.IsConv)
903         NewOpenCLBuiltin->addAttr(ConvergentAttr::CreateImplicit(Context));
904 
905       if (!S.getLangOpts().OpenCLCPlusPlus)
906         NewOpenCLBuiltin->addAttr(OverloadableAttr::CreateImplicit(Context));
907 
908       LR.addDecl(NewOpenCLBuiltin);
909     }
910   }
911 
912   // If we added overloads, need to resolve the lookup result.
913   if (Len > 1 || HasGenType)
914     LR.resolveKind();
915 }
916 
917 bool Sema::LookupBuiltin(LookupResult &R) {
918   Sema::LookupNameKind NameKind = R.getLookupKind();
919 
920   // If we didn't find a use of this identifier, and if the identifier
921   // corresponds to a compiler builtin, create the decl object for the builtin
922   // now, injecting it into translation unit scope, and return it.
923   if (NameKind == Sema::LookupOrdinaryName ||
924       NameKind == Sema::LookupRedeclarationWithLinkage) {
925     IdentifierInfo *II = R.getLookupName().getAsIdentifierInfo();
926     if (II) {
927       if (getLangOpts().CPlusPlus && NameKind == Sema::LookupOrdinaryName) {
928         if (II == getASTContext().getMakeIntegerSeqName()) {
929           R.addDecl(getASTContext().getMakeIntegerSeqDecl());
930           return true;
931         } else if (II == getASTContext().getTypePackElementName()) {
932           R.addDecl(getASTContext().getTypePackElementDecl());
933           return true;
934         }
935       }
936 
937       // Check if this is an OpenCL Builtin, and if so, insert its overloads.
938       if (getLangOpts().OpenCL && getLangOpts().DeclareOpenCLBuiltins) {
939         auto Index = isOpenCLBuiltin(II->getName());
940         if (Index.first) {
941           InsertOCLBuiltinDeclarationsFromTable(*this, R, II, Index.first - 1,
942                                                 Index.second);
943           return true;
944         }
945       }
946 
947       if (RISCV().DeclareRVVBuiltins || RISCV().DeclareSiFiveVectorBuiltins) {
948         if (!RISCV().IntrinsicManager)
949           RISCV().IntrinsicManager = CreateRISCVIntrinsicManager(*this);
950 
951         RISCV().IntrinsicManager->InitIntrinsicList();
952 
953         if (RISCV().IntrinsicManager->CreateIntrinsicIfFound(R, II, PP))
954           return true;
955       }
956 
957       // If this is a builtin on this (or all) targets, create the decl.
958       if (unsigned BuiltinID = II->getBuiltinID()) {
959         // In C++ and OpenCL (spec v1.2 s6.9.f), we don't have any predefined
960         // library functions like 'malloc'. Instead, we'll just error.
961         if ((getLangOpts().CPlusPlus || getLangOpts().OpenCL) &&
962             Context.BuiltinInfo.isPredefinedLibFunction(BuiltinID))
963           return false;
964 
965         if (NamedDecl *D =
966                 LazilyCreateBuiltin(II, BuiltinID, TUScope,
967                                     R.isForRedeclaration(), R.getNameLoc())) {
968           R.addDecl(D);
969           return true;
970         }
971       }
972     }
973   }
974 
975   return false;
976 }
977 
978 /// Looks up the declaration of "struct objc_super" and
979 /// saves it for later use in building builtin declaration of
980 /// objc_msgSendSuper and objc_msgSendSuper_stret.
981 static void LookupPredefedObjCSuperType(Sema &Sema, Scope *S) {
982   ASTContext &Context = Sema.Context;
983   LookupResult Result(Sema, &Context.Idents.get("objc_super"), SourceLocation(),
984                       Sema::LookupTagName);
985   Sema.LookupName(Result, S);
986   if (Result.getResultKind() == LookupResult::Found)
987     if (const TagDecl *TD = Result.getAsSingle<TagDecl>())
988       Context.setObjCSuperType(Context.getTagDeclType(TD));
989 }
990 
991 void Sema::LookupNecessaryTypesForBuiltin(Scope *S, unsigned ID) {
992   if (ID == Builtin::BIobjc_msgSendSuper)
993     LookupPredefedObjCSuperType(*this, S);
994 }
995 
996 /// Determine whether we can declare a special member function within
997 /// the class at this point.
998 static bool CanDeclareSpecialMemberFunction(const CXXRecordDecl *Class) {
999   // We need to have a definition for the class.
1000   if (!Class->getDefinition() || Class->isDependentContext())
1001     return false;
1002 
1003   // We can't be in the middle of defining the class.
1004   return !Class->isBeingDefined();
1005 }
1006 
1007 void Sema::ForceDeclarationOfImplicitMembers(CXXRecordDecl *Class) {
1008   if (!CanDeclareSpecialMemberFunction(Class))
1009     return;
1010 
1011   // If the default constructor has not yet been declared, do so now.
1012   if (Class->needsImplicitDefaultConstructor())
1013     DeclareImplicitDefaultConstructor(Class);
1014 
1015   // If the copy constructor has not yet been declared, do so now.
1016   if (Class->needsImplicitCopyConstructor())
1017     DeclareImplicitCopyConstructor(Class);
1018 
1019   // If the copy assignment operator has not yet been declared, do so now.
1020   if (Class->needsImplicitCopyAssignment())
1021     DeclareImplicitCopyAssignment(Class);
1022 
1023   if (getLangOpts().CPlusPlus11) {
1024     // If the move constructor has not yet been declared, do so now.
1025     if (Class->needsImplicitMoveConstructor())
1026       DeclareImplicitMoveConstructor(Class);
1027 
1028     // If the move assignment operator has not yet been declared, do so now.
1029     if (Class->needsImplicitMoveAssignment())
1030       DeclareImplicitMoveAssignment(Class);
1031   }
1032 
1033   // If the destructor has not yet been declared, do so now.
1034   if (Class->needsImplicitDestructor())
1035     DeclareImplicitDestructor(Class);
1036 }
1037 
1038 /// Determine whether this is the name of an implicitly-declared
1039 /// special member function.
1040 static bool isImplicitlyDeclaredMemberFunctionName(DeclarationName Name) {
1041   switch (Name.getNameKind()) {
1042   case DeclarationName::CXXConstructorName:
1043   case DeclarationName::CXXDestructorName:
1044     return true;
1045 
1046   case DeclarationName::CXXOperatorName:
1047     return Name.getCXXOverloadedOperator() == OO_Equal;
1048 
1049   default:
1050     break;
1051   }
1052 
1053   return false;
1054 }
1055 
1056 /// If there are any implicit member functions with the given name
1057 /// that need to be declared in the given declaration context, do so.
1058 static void DeclareImplicitMemberFunctionsWithName(Sema &S,
1059                                                    DeclarationName Name,
1060                                                    SourceLocation Loc,
1061                                                    const DeclContext *DC) {
1062   if (!DC)
1063     return;
1064 
1065   switch (Name.getNameKind()) {
1066   case DeclarationName::CXXConstructorName:
1067     if (const CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(DC))
1068       if (Record->getDefinition() && CanDeclareSpecialMemberFunction(Record)) {
1069         CXXRecordDecl *Class = const_cast<CXXRecordDecl *>(Record);
1070         if (Record->needsImplicitDefaultConstructor())
1071           S.DeclareImplicitDefaultConstructor(Class);
1072         if (Record->needsImplicitCopyConstructor())
1073           S.DeclareImplicitCopyConstructor(Class);
1074         if (S.getLangOpts().CPlusPlus11 &&
1075             Record->needsImplicitMoveConstructor())
1076           S.DeclareImplicitMoveConstructor(Class);
1077       }
1078     break;
1079 
1080   case DeclarationName::CXXDestructorName:
1081     if (const CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(DC))
1082       if (Record->getDefinition() && Record->needsImplicitDestructor() &&
1083           CanDeclareSpecialMemberFunction(Record))
1084         S.DeclareImplicitDestructor(const_cast<CXXRecordDecl *>(Record));
1085     break;
1086 
1087   case DeclarationName::CXXOperatorName:
1088     if (Name.getCXXOverloadedOperator() != OO_Equal)
1089       break;
1090 
1091     if (const CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(DC)) {
1092       if (Record->getDefinition() && CanDeclareSpecialMemberFunction(Record)) {
1093         CXXRecordDecl *Class = const_cast<CXXRecordDecl *>(Record);
1094         if (Record->needsImplicitCopyAssignment())
1095           S.DeclareImplicitCopyAssignment(Class);
1096         if (S.getLangOpts().CPlusPlus11 &&
1097             Record->needsImplicitMoveAssignment())
1098           S.DeclareImplicitMoveAssignment(Class);
1099       }
1100     }
1101     break;
1102 
1103   case DeclarationName::CXXDeductionGuideName:
1104     S.DeclareImplicitDeductionGuides(Name.getCXXDeductionGuideTemplate(), Loc);
1105     break;
1106 
1107   default:
1108     break;
1109   }
1110 }
1111 
1112 // Adds all qualifying matches for a name within a decl context to the
1113 // given lookup result.  Returns true if any matches were found.
1114 static bool LookupDirect(Sema &S, LookupResult &R, const DeclContext *DC) {
1115   bool Found = false;
1116 
1117   // Lazily declare C++ special member functions.
1118   if (S.getLangOpts().CPlusPlus)
1119     DeclareImplicitMemberFunctionsWithName(S, R.getLookupName(), R.getNameLoc(),
1120                                            DC);
1121 
1122   // Perform lookup into this declaration context.
1123   DeclContext::lookup_result DR = DC->lookup(R.getLookupName());
1124   for (NamedDecl *D : DR) {
1125     if ((D = R.getAcceptableDecl(D))) {
1126       R.addDecl(D);
1127       Found = true;
1128     }
1129   }
1130 
1131   if (!Found && DC->isTranslationUnit() && S.LookupBuiltin(R))
1132     return true;
1133 
1134   if (R.getLookupName().getNameKind()
1135         != DeclarationName::CXXConversionFunctionName ||
1136       R.getLookupName().getCXXNameType()->isDependentType() ||
1137       !isa<CXXRecordDecl>(DC))
1138     return Found;
1139 
1140   // C++ [temp.mem]p6:
1141   //   A specialization of a conversion function template is not found by
1142   //   name lookup. Instead, any conversion function templates visible in the
1143   //   context of the use are considered. [...]
1144   const CXXRecordDecl *Record = cast<CXXRecordDecl>(DC);
1145   if (!Record->isCompleteDefinition())
1146     return Found;
1147 
1148   // For conversion operators, 'operator auto' should only match
1149   // 'operator auto'.  Since 'auto' is not a type, it shouldn't be considered
1150   // as a candidate for template substitution.
1151   auto *ContainedDeducedType =
1152       R.getLookupName().getCXXNameType()->getContainedDeducedType();
1153   if (R.getLookupName().getNameKind() ==
1154           DeclarationName::CXXConversionFunctionName &&
1155       ContainedDeducedType && ContainedDeducedType->isUndeducedType())
1156     return Found;
1157 
1158   for (CXXRecordDecl::conversion_iterator U = Record->conversion_begin(),
1159          UEnd = Record->conversion_end(); U != UEnd; ++U) {
1160     FunctionTemplateDecl *ConvTemplate = dyn_cast<FunctionTemplateDecl>(*U);
1161     if (!ConvTemplate)
1162       continue;
1163 
1164     // When we're performing lookup for the purposes of redeclaration, just
1165     // add the conversion function template. When we deduce template
1166     // arguments for specializations, we'll end up unifying the return
1167     // type of the new declaration with the type of the function template.
1168     if (R.isForRedeclaration()) {
1169       R.addDecl(ConvTemplate);
1170       Found = true;
1171       continue;
1172     }
1173 
1174     // C++ [temp.mem]p6:
1175     //   [...] For each such operator, if argument deduction succeeds
1176     //   (14.9.2.3), the resulting specialization is used as if found by
1177     //   name lookup.
1178     //
1179     // When referencing a conversion function for any purpose other than
1180     // a redeclaration (such that we'll be building an expression with the
1181     // result), perform template argument deduction and place the
1182     // specialization into the result set. We do this to avoid forcing all
1183     // callers to perform special deduction for conversion functions.
1184     TemplateDeductionInfo Info(R.getNameLoc());
1185     FunctionDecl *Specialization = nullptr;
1186 
1187     const FunctionProtoType *ConvProto
1188       = ConvTemplate->getTemplatedDecl()->getType()->getAs<FunctionProtoType>();
1189     assert(ConvProto && "Nonsensical conversion function template type");
1190 
1191     // Compute the type of the function that we would expect the conversion
1192     // function to have, if it were to match the name given.
1193     // FIXME: Calling convention!
1194     FunctionProtoType::ExtProtoInfo EPI = ConvProto->getExtProtoInfo();
1195     EPI.ExtInfo = EPI.ExtInfo.withCallingConv(CC_C);
1196     EPI.ExceptionSpec = EST_None;
1197     QualType ExpectedType = R.getSema().Context.getFunctionType(
1198         R.getLookupName().getCXXNameType(), std::nullopt, EPI);
1199 
1200     // Perform template argument deduction against the type that we would
1201     // expect the function to have.
1202     if (R.getSema().DeduceTemplateArguments(ConvTemplate, nullptr, ExpectedType,
1203                                             Specialization, Info) ==
1204         TemplateDeductionResult::Success) {
1205       R.addDecl(Specialization);
1206       Found = true;
1207     }
1208   }
1209 
1210   return Found;
1211 }
1212 
1213 // Performs C++ unqualified lookup into the given file context.
1214 static bool CppNamespaceLookup(Sema &S, LookupResult &R, ASTContext &Context,
1215                                const DeclContext *NS,
1216                                UnqualUsingDirectiveSet &UDirs) {
1217 
1218   assert(NS && NS->isFileContext() && "CppNamespaceLookup() requires namespace!");
1219 
1220   // Perform direct name lookup into the LookupCtx.
1221   bool Found = LookupDirect(S, R, NS);
1222 
1223   // Perform direct name lookup into the namespaces nominated by the
1224   // using directives whose common ancestor is this namespace.
1225   for (const UnqualUsingEntry &UUE : UDirs.getNamespacesFor(NS))
1226     if (LookupDirect(S, R, UUE.getNominatedNamespace()))
1227       Found = true;
1228 
1229   R.resolveKind();
1230 
1231   return Found;
1232 }
1233 
1234 static bool isNamespaceOrTranslationUnitScope(Scope *S) {
1235   if (DeclContext *Ctx = S->getEntity())
1236     return Ctx->isFileContext();
1237   return false;
1238 }
1239 
1240 /// Find the outer declaration context from this scope. This indicates the
1241 /// context that we should search up to (exclusive) before considering the
1242 /// parent of the specified scope.
1243 static DeclContext *findOuterContext(Scope *S) {
1244   for (Scope *OuterS = S->getParent(); OuterS; OuterS = OuterS->getParent())
1245     if (DeclContext *DC = OuterS->getLookupEntity())
1246       return DC;
1247   return nullptr;
1248 }
1249 
1250 namespace {
1251 /// An RAII object to specify that we want to find block scope extern
1252 /// declarations.
1253 struct FindLocalExternScope {
1254   FindLocalExternScope(LookupResult &R)
1255       : R(R), OldFindLocalExtern(R.getIdentifierNamespace() &
1256                                  Decl::IDNS_LocalExtern) {
1257     R.setFindLocalExtern(R.getIdentifierNamespace() &
1258                          (Decl::IDNS_Ordinary | Decl::IDNS_NonMemberOperator));
1259   }
1260   void restore() {
1261     R.setFindLocalExtern(OldFindLocalExtern);
1262   }
1263   ~FindLocalExternScope() {
1264     restore();
1265   }
1266   LookupResult &R;
1267   bool OldFindLocalExtern;
1268 };
1269 } // end anonymous namespace
1270 
1271 bool Sema::CppLookupName(LookupResult &R, Scope *S) {
1272   assert(getLangOpts().CPlusPlus && "Can perform only C++ lookup");
1273 
1274   DeclarationName Name = R.getLookupName();
1275   Sema::LookupNameKind NameKind = R.getLookupKind();
1276 
1277   // If this is the name of an implicitly-declared special member function,
1278   // go through the scope stack to implicitly declare
1279   if (isImplicitlyDeclaredMemberFunctionName(Name)) {
1280     for (Scope *PreS = S; PreS; PreS = PreS->getParent())
1281       if (DeclContext *DC = PreS->getEntity())
1282         DeclareImplicitMemberFunctionsWithName(*this, Name, R.getNameLoc(), DC);
1283   }
1284 
1285   // C++23 [temp.dep.general]p2:
1286   //   The component name of an unqualified-id is dependent if
1287   //   - it is a conversion-function-id whose conversion-type-id
1288   //     is dependent, or
1289   //   - it is operator= and the current class is a templated entity, or
1290   //   - the unqualified-id is the postfix-expression in a dependent call.
1291   if (Name.getNameKind() == DeclarationName::CXXConversionFunctionName &&
1292       Name.getCXXNameType()->isDependentType()) {
1293     R.setNotFoundInCurrentInstantiation();
1294     return false;
1295   }
1296 
1297   // Implicitly declare member functions with the name we're looking for, if in
1298   // fact we are in a scope where it matters.
1299 
1300   Scope *Initial = S;
1301   IdentifierResolver::iterator
1302     I = IdResolver.begin(Name),
1303     IEnd = IdResolver.end();
1304 
1305   // First we lookup local scope.
1306   // We don't consider using-directives, as per 7.3.4.p1 [namespace.udir]
1307   // ...During unqualified name lookup (3.4.1), the names appear as if
1308   // they were declared in the nearest enclosing namespace which contains
1309   // both the using-directive and the nominated namespace.
1310   // [Note: in this context, "contains" means "contains directly or
1311   // indirectly".
1312   //
1313   // For example:
1314   // namespace A { int i; }
1315   // void foo() {
1316   //   int i;
1317   //   {
1318   //     using namespace A;
1319   //     ++i; // finds local 'i', A::i appears at global scope
1320   //   }
1321   // }
1322   //
1323   UnqualUsingDirectiveSet UDirs(*this);
1324   bool VisitedUsingDirectives = false;
1325   bool LeftStartingScope = false;
1326 
1327   // When performing a scope lookup, we want to find local extern decls.
1328   FindLocalExternScope FindLocals(R);
1329 
1330   for (; S && !isNamespaceOrTranslationUnitScope(S); S = S->getParent()) {
1331     bool SearchNamespaceScope = true;
1332     // Check whether the IdResolver has anything in this scope.
1333     for (; I != IEnd && S->isDeclScope(*I); ++I) {
1334       if (NamedDecl *ND = R.getAcceptableDecl(*I)) {
1335         if (NameKind == LookupRedeclarationWithLinkage &&
1336             !(*I)->isTemplateParameter()) {
1337           // If it's a template parameter, we still find it, so we can diagnose
1338           // the invalid redeclaration.
1339 
1340           // Determine whether this (or a previous) declaration is
1341           // out-of-scope.
1342           if (!LeftStartingScope && !Initial->isDeclScope(*I))
1343             LeftStartingScope = true;
1344 
1345           // If we found something outside of our starting scope that
1346           // does not have linkage, skip it.
1347           if (LeftStartingScope && !((*I)->hasLinkage())) {
1348             R.setShadowed();
1349             continue;
1350           }
1351         } else {
1352           // We found something in this scope, we should not look at the
1353           // namespace scope
1354           SearchNamespaceScope = false;
1355         }
1356         R.addDecl(ND);
1357       }
1358     }
1359     if (!SearchNamespaceScope) {
1360       R.resolveKind();
1361       if (S->isClassScope())
1362         if (auto *Record = dyn_cast_if_present<CXXRecordDecl>(S->getEntity()))
1363           R.setNamingClass(Record);
1364       return true;
1365     }
1366 
1367     if (NameKind == LookupLocalFriendName && !S->isClassScope()) {
1368       // C++11 [class.friend]p11:
1369       //   If a friend declaration appears in a local class and the name
1370       //   specified is an unqualified name, a prior declaration is
1371       //   looked up without considering scopes that are outside the
1372       //   innermost enclosing non-class scope.
1373       return false;
1374     }
1375 
1376     if (DeclContext *Ctx = S->getLookupEntity()) {
1377       DeclContext *OuterCtx = findOuterContext(S);
1378       for (; Ctx && !Ctx->Equals(OuterCtx); Ctx = Ctx->getLookupParent()) {
1379         // We do not directly look into transparent contexts, since
1380         // those entities will be found in the nearest enclosing
1381         // non-transparent context.
1382         if (Ctx->isTransparentContext())
1383           continue;
1384 
1385         // We do not look directly into function or method contexts,
1386         // since all of the local variables and parameters of the
1387         // function/method are present within the Scope.
1388         if (Ctx->isFunctionOrMethod()) {
1389           // If we have an Objective-C instance method, look for ivars
1390           // in the corresponding interface.
1391           if (ObjCMethodDecl *Method = dyn_cast<ObjCMethodDecl>(Ctx)) {
1392             if (Method->isInstanceMethod() && Name.getAsIdentifierInfo())
1393               if (ObjCInterfaceDecl *Class = Method->getClassInterface()) {
1394                 ObjCInterfaceDecl *ClassDeclared;
1395                 if (ObjCIvarDecl *Ivar = Class->lookupInstanceVariable(
1396                                                  Name.getAsIdentifierInfo(),
1397                                                              ClassDeclared)) {
1398                   if (NamedDecl *ND = R.getAcceptableDecl(Ivar)) {
1399                     R.addDecl(ND);
1400                     R.resolveKind();
1401                     return true;
1402                   }
1403                 }
1404               }
1405           }
1406 
1407           continue;
1408         }
1409 
1410         // If this is a file context, we need to perform unqualified name
1411         // lookup considering using directives.
1412         if (Ctx->isFileContext()) {
1413           // If we haven't handled using directives yet, do so now.
1414           if (!VisitedUsingDirectives) {
1415             // Add using directives from this context up to the top level.
1416             for (DeclContext *UCtx = Ctx; UCtx; UCtx = UCtx->getParent()) {
1417               if (UCtx->isTransparentContext())
1418                 continue;
1419 
1420               UDirs.visit(UCtx, UCtx);
1421             }
1422 
1423             // Find the innermost file scope, so we can add using directives
1424             // from local scopes.
1425             Scope *InnermostFileScope = S;
1426             while (InnermostFileScope &&
1427                    !isNamespaceOrTranslationUnitScope(InnermostFileScope))
1428               InnermostFileScope = InnermostFileScope->getParent();
1429             UDirs.visitScopeChain(Initial, InnermostFileScope);
1430 
1431             UDirs.done();
1432 
1433             VisitedUsingDirectives = true;
1434           }
1435 
1436           if (CppNamespaceLookup(*this, R, Context, Ctx, UDirs)) {
1437             R.resolveKind();
1438             return true;
1439           }
1440 
1441           continue;
1442         }
1443 
1444         // Perform qualified name lookup into this context.
1445         // FIXME: In some cases, we know that every name that could be found by
1446         // this qualified name lookup will also be on the identifier chain. For
1447         // example, inside a class without any base classes, we never need to
1448         // perform qualified lookup because all of the members are on top of the
1449         // identifier chain.
1450         if (LookupQualifiedName(R, Ctx, /*InUnqualifiedLookup=*/true))
1451           return true;
1452       }
1453     }
1454   }
1455 
1456   // Stop if we ran out of scopes.
1457   // FIXME:  This really, really shouldn't be happening.
1458   if (!S) return false;
1459 
1460   // If we are looking for members, no need to look into global/namespace scope.
1461   if (NameKind == LookupMemberName)
1462     return false;
1463 
1464   // Collect UsingDirectiveDecls in all scopes, and recursively all
1465   // nominated namespaces by those using-directives.
1466   //
1467   // FIXME: Cache this sorted list in Scope structure, and DeclContext, so we
1468   // don't build it for each lookup!
1469   if (!VisitedUsingDirectives) {
1470     UDirs.visitScopeChain(Initial, S);
1471     UDirs.done();
1472   }
1473 
1474   // If we're not performing redeclaration lookup, do not look for local
1475   // extern declarations outside of a function scope.
1476   if (!R.isForRedeclaration())
1477     FindLocals.restore();
1478 
1479   // Lookup namespace scope, and global scope.
1480   // Unqualified name lookup in C++ requires looking into scopes
1481   // that aren't strictly lexical, and therefore we walk through the
1482   // context as well as walking through the scopes.
1483   for (; S; S = S->getParent()) {
1484     // Check whether the IdResolver has anything in this scope.
1485     bool Found = false;
1486     for (; I != IEnd && S->isDeclScope(*I); ++I) {
1487       if (NamedDecl *ND = R.getAcceptableDecl(*I)) {
1488         // We found something.  Look for anything else in our scope
1489         // with this same name and in an acceptable identifier
1490         // namespace, so that we can construct an overload set if we
1491         // need to.
1492         Found = true;
1493         R.addDecl(ND);
1494       }
1495     }
1496 
1497     if (Found && S->isTemplateParamScope()) {
1498       R.resolveKind();
1499       return true;
1500     }
1501 
1502     DeclContext *Ctx = S->getLookupEntity();
1503     if (Ctx) {
1504       DeclContext *OuterCtx = findOuterContext(S);
1505       for (; Ctx && !Ctx->Equals(OuterCtx); Ctx = Ctx->getLookupParent()) {
1506         // We do not directly look into transparent contexts, since
1507         // those entities will be found in the nearest enclosing
1508         // non-transparent context.
1509         if (Ctx->isTransparentContext())
1510           continue;
1511 
1512         // If we have a context, and it's not a context stashed in the
1513         // template parameter scope for an out-of-line definition, also
1514         // look into that context.
1515         if (!(Found && S->isTemplateParamScope())) {
1516           assert(Ctx->isFileContext() &&
1517               "We should have been looking only at file context here already.");
1518 
1519           // Look into context considering using-directives.
1520           if (CppNamespaceLookup(*this, R, Context, Ctx, UDirs))
1521             Found = true;
1522         }
1523 
1524         if (Found) {
1525           R.resolveKind();
1526           return true;
1527         }
1528 
1529         if (R.isForRedeclaration() && !Ctx->isTransparentContext())
1530           return false;
1531       }
1532     }
1533 
1534     if (R.isForRedeclaration() && Ctx && !Ctx->isTransparentContext())
1535       return false;
1536   }
1537 
1538   return !R.empty();
1539 }
1540 
1541 void Sema::makeMergedDefinitionVisible(NamedDecl *ND) {
1542   if (auto *M = getCurrentModule())
1543     Context.mergeDefinitionIntoModule(ND, M);
1544   else
1545     // We're not building a module; just make the definition visible.
1546     ND->setVisibleDespiteOwningModule();
1547 
1548   // If ND is a template declaration, make the template parameters
1549   // visible too. They're not (necessarily) within a mergeable DeclContext.
1550   if (auto *TD = dyn_cast<TemplateDecl>(ND))
1551     for (auto *Param : *TD->getTemplateParameters())
1552       makeMergedDefinitionVisible(Param);
1553 }
1554 
1555 /// Find the module in which the given declaration was defined.
1556 static Module *getDefiningModule(Sema &S, Decl *Entity) {
1557   if (FunctionDecl *FD = dyn_cast<FunctionDecl>(Entity)) {
1558     // If this function was instantiated from a template, the defining module is
1559     // the module containing the pattern.
1560     if (FunctionDecl *Pattern = FD->getTemplateInstantiationPattern())
1561       Entity = Pattern;
1562   } else if (CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(Entity)) {
1563     if (CXXRecordDecl *Pattern = RD->getTemplateInstantiationPattern())
1564       Entity = Pattern;
1565   } else if (EnumDecl *ED = dyn_cast<EnumDecl>(Entity)) {
1566     if (auto *Pattern = ED->getTemplateInstantiationPattern())
1567       Entity = Pattern;
1568   } else if (VarDecl *VD = dyn_cast<VarDecl>(Entity)) {
1569     if (VarDecl *Pattern = VD->getTemplateInstantiationPattern())
1570       Entity = Pattern;
1571   }
1572 
1573   // Walk up to the containing context. That might also have been instantiated
1574   // from a template.
1575   DeclContext *Context = Entity->getLexicalDeclContext();
1576   if (Context->isFileContext())
1577     return S.getOwningModule(Entity);
1578   return getDefiningModule(S, cast<Decl>(Context));
1579 }
1580 
1581 llvm::DenseSet<Module*> &Sema::getLookupModules() {
1582   unsigned N = CodeSynthesisContexts.size();
1583   for (unsigned I = CodeSynthesisContextLookupModules.size();
1584        I != N; ++I) {
1585     Module *M = CodeSynthesisContexts[I].Entity ?
1586                 getDefiningModule(*this, CodeSynthesisContexts[I].Entity) :
1587                 nullptr;
1588     if (M && !LookupModulesCache.insert(M).second)
1589       M = nullptr;
1590     CodeSynthesisContextLookupModules.push_back(M);
1591   }
1592   return LookupModulesCache;
1593 }
1594 
1595 bool Sema::isUsableModule(const Module *M) {
1596   assert(M && "We shouldn't check nullness for module here");
1597   // Return quickly if we cached the result.
1598   if (UsableModuleUnitsCache.count(M))
1599     return true;
1600 
1601   // If M is the global module fragment of the current translation unit. So it
1602   // should be usable.
1603   // [module.global.frag]p1:
1604   //   The global module fragment can be used to provide declarations that are
1605   //   attached to the global module and usable within the module unit.
1606   if (M == TheGlobalModuleFragment || M == TheImplicitGlobalModuleFragment) {
1607     UsableModuleUnitsCache.insert(M);
1608     return true;
1609   }
1610 
1611   // Otherwise, the global module fragment from other translation unit is not
1612   // directly usable.
1613   if (M->isGlobalModule())
1614     return false;
1615 
1616   Module *Current = getCurrentModule();
1617 
1618   // If we're not parsing a module, we can't use all the declarations from
1619   // another module easily.
1620   if (!Current)
1621     return false;
1622 
1623   // If M is the module we're parsing or M and the current module unit lives in
1624   // the same module, M should be usable.
1625   //
1626   // Note: It should be fine to search the vector `ModuleScopes` linearly since
1627   // it should be generally small enough. There should be rare module fragments
1628   // in a named module unit.
1629   if (llvm::count_if(ModuleScopes,
1630                      [&M](const ModuleScope &MS) { return MS.Module == M; }) ||
1631       getASTContext().isInSameModule(M, Current)) {
1632     UsableModuleUnitsCache.insert(M);
1633     return true;
1634   }
1635 
1636   return false;
1637 }
1638 
1639 bool Sema::hasVisibleMergedDefinition(const NamedDecl *Def) {
1640   for (const Module *Merged : Context.getModulesWithMergedDefinition(Def))
1641     if (isModuleVisible(Merged))
1642       return true;
1643   return false;
1644 }
1645 
1646 bool Sema::hasMergedDefinitionInCurrentModule(const NamedDecl *Def) {
1647   for (const Module *Merged : Context.getModulesWithMergedDefinition(Def))
1648     if (isUsableModule(Merged))
1649       return true;
1650   return false;
1651 }
1652 
1653 template <typename ParmDecl>
1654 static bool
1655 hasAcceptableDefaultArgument(Sema &S, const ParmDecl *D,
1656                              llvm::SmallVectorImpl<Module *> *Modules,
1657                              Sema::AcceptableKind Kind) {
1658   if (!D->hasDefaultArgument())
1659     return false;
1660 
1661   llvm::SmallPtrSet<const ParmDecl *, 4> Visited;
1662   while (D && Visited.insert(D).second) {
1663     auto &DefaultArg = D->getDefaultArgStorage();
1664     if (!DefaultArg.isInherited() && S.isAcceptable(D, Kind))
1665       return true;
1666 
1667     if (!DefaultArg.isInherited() && Modules) {
1668       auto *NonConstD = const_cast<ParmDecl*>(D);
1669       Modules->push_back(S.getOwningModule(NonConstD));
1670     }
1671 
1672     // If there was a previous default argument, maybe its parameter is
1673     // acceptable.
1674     D = DefaultArg.getInheritedFrom();
1675   }
1676   return false;
1677 }
1678 
1679 bool Sema::hasAcceptableDefaultArgument(
1680     const NamedDecl *D, llvm::SmallVectorImpl<Module *> *Modules,
1681     Sema::AcceptableKind Kind) {
1682   if (auto *P = dyn_cast<TemplateTypeParmDecl>(D))
1683     return ::hasAcceptableDefaultArgument(*this, P, Modules, Kind);
1684 
1685   if (auto *P = dyn_cast<NonTypeTemplateParmDecl>(D))
1686     return ::hasAcceptableDefaultArgument(*this, P, Modules, Kind);
1687 
1688   return ::hasAcceptableDefaultArgument(
1689       *this, cast<TemplateTemplateParmDecl>(D), Modules, Kind);
1690 }
1691 
1692 bool Sema::hasVisibleDefaultArgument(const NamedDecl *D,
1693                                      llvm::SmallVectorImpl<Module *> *Modules) {
1694   return hasAcceptableDefaultArgument(D, Modules,
1695                                       Sema::AcceptableKind::Visible);
1696 }
1697 
1698 bool Sema::hasReachableDefaultArgument(
1699     const NamedDecl *D, llvm::SmallVectorImpl<Module *> *Modules) {
1700   return hasAcceptableDefaultArgument(D, Modules,
1701                                       Sema::AcceptableKind::Reachable);
1702 }
1703 
1704 template <typename Filter>
1705 static bool
1706 hasAcceptableDeclarationImpl(Sema &S, const NamedDecl *D,
1707                              llvm::SmallVectorImpl<Module *> *Modules, Filter F,
1708                              Sema::AcceptableKind Kind) {
1709   bool HasFilteredRedecls = false;
1710 
1711   for (auto *Redecl : D->redecls()) {
1712     auto *R = cast<NamedDecl>(Redecl);
1713     if (!F(R))
1714       continue;
1715 
1716     if (S.isAcceptable(R, Kind))
1717       return true;
1718 
1719     HasFilteredRedecls = true;
1720 
1721     if (Modules)
1722       Modules->push_back(R->getOwningModule());
1723   }
1724 
1725   // Only return false if there is at least one redecl that is not filtered out.
1726   if (HasFilteredRedecls)
1727     return false;
1728 
1729   return true;
1730 }
1731 
1732 static bool
1733 hasAcceptableExplicitSpecialization(Sema &S, const NamedDecl *D,
1734                                     llvm::SmallVectorImpl<Module *> *Modules,
1735                                     Sema::AcceptableKind Kind) {
1736   return hasAcceptableDeclarationImpl(
1737       S, D, Modules,
1738       [](const NamedDecl *D) {
1739         if (auto *RD = dyn_cast<CXXRecordDecl>(D))
1740           return RD->getTemplateSpecializationKind() ==
1741                  TSK_ExplicitSpecialization;
1742         if (auto *FD = dyn_cast<FunctionDecl>(D))
1743           return FD->getTemplateSpecializationKind() ==
1744                  TSK_ExplicitSpecialization;
1745         if (auto *VD = dyn_cast<VarDecl>(D))
1746           return VD->getTemplateSpecializationKind() ==
1747                  TSK_ExplicitSpecialization;
1748         llvm_unreachable("unknown explicit specialization kind");
1749       },
1750       Kind);
1751 }
1752 
1753 bool Sema::hasVisibleExplicitSpecialization(
1754     const NamedDecl *D, llvm::SmallVectorImpl<Module *> *Modules) {
1755   return ::hasAcceptableExplicitSpecialization(*this, D, Modules,
1756                                                Sema::AcceptableKind::Visible);
1757 }
1758 
1759 bool Sema::hasReachableExplicitSpecialization(
1760     const NamedDecl *D, llvm::SmallVectorImpl<Module *> *Modules) {
1761   return ::hasAcceptableExplicitSpecialization(*this, D, Modules,
1762                                                Sema::AcceptableKind::Reachable);
1763 }
1764 
1765 static bool
1766 hasAcceptableMemberSpecialization(Sema &S, const NamedDecl *D,
1767                                   llvm::SmallVectorImpl<Module *> *Modules,
1768                                   Sema::AcceptableKind Kind) {
1769   assert(isa<CXXRecordDecl>(D->getDeclContext()) &&
1770          "not a member specialization");
1771   return hasAcceptableDeclarationImpl(
1772       S, D, Modules,
1773       [](const NamedDecl *D) {
1774         // If the specialization is declared at namespace scope, then it's a
1775         // member specialization declaration. If it's lexically inside the class
1776         // definition then it was instantiated.
1777         //
1778         // FIXME: This is a hack. There should be a better way to determine
1779         // this.
1780         // FIXME: What about MS-style explicit specializations declared within a
1781         //        class definition?
1782         return D->getLexicalDeclContext()->isFileContext();
1783       },
1784       Kind);
1785 }
1786 
1787 bool Sema::hasVisibleMemberSpecialization(
1788     const NamedDecl *D, llvm::SmallVectorImpl<Module *> *Modules) {
1789   return hasAcceptableMemberSpecialization(*this, D, Modules,
1790                                            Sema::AcceptableKind::Visible);
1791 }
1792 
1793 bool Sema::hasReachableMemberSpecialization(
1794     const NamedDecl *D, llvm::SmallVectorImpl<Module *> *Modules) {
1795   return hasAcceptableMemberSpecialization(*this, D, Modules,
1796                                            Sema::AcceptableKind::Reachable);
1797 }
1798 
1799 /// Determine whether a declaration is acceptable to name lookup.
1800 ///
1801 /// This routine determines whether the declaration D is acceptable in the
1802 /// current lookup context, taking into account the current template
1803 /// instantiation stack. During template instantiation, a declaration is
1804 /// acceptable if it is acceptable from a module containing any entity on the
1805 /// template instantiation path (by instantiating a template, you allow it to
1806 /// see the declarations that your module can see, including those later on in
1807 /// your module).
1808 bool LookupResult::isAcceptableSlow(Sema &SemaRef, NamedDecl *D,
1809                                     Sema::AcceptableKind Kind) {
1810   assert(!D->isUnconditionallyVisible() &&
1811          "should not call this: not in slow case");
1812 
1813   Module *DeclModule = SemaRef.getOwningModule(D);
1814   assert(DeclModule && "hidden decl has no owning module");
1815 
1816   // If the owning module is visible, the decl is acceptable.
1817   if (SemaRef.isModuleVisible(DeclModule,
1818                               D->isInvisibleOutsideTheOwningModule()))
1819     return true;
1820 
1821   // Determine whether a decl context is a file context for the purpose of
1822   // visibility/reachability. This looks through some (export and linkage spec)
1823   // transparent contexts, but not others (enums).
1824   auto IsEffectivelyFileContext = [](const DeclContext *DC) {
1825     return DC->isFileContext() || isa<LinkageSpecDecl>(DC) ||
1826            isa<ExportDecl>(DC);
1827   };
1828 
1829   // If this declaration is not at namespace scope
1830   // then it is acceptable if its lexical parent has a acceptable definition.
1831   DeclContext *DC = D->getLexicalDeclContext();
1832   if (DC && !IsEffectivelyFileContext(DC)) {
1833     // For a parameter, check whether our current template declaration's
1834     // lexical context is acceptable, not whether there's some other acceptable
1835     // definition of it, because parameters aren't "within" the definition.
1836     //
1837     // In C++ we need to check for a acceptable definition due to ODR merging,
1838     // and in C we must not because each declaration of a function gets its own
1839     // set of declarations for tags in prototype scope.
1840     bool AcceptableWithinParent;
1841     if (D->isTemplateParameter()) {
1842       bool SearchDefinitions = true;
1843       if (const auto *DCD = dyn_cast<Decl>(DC)) {
1844         if (const auto *TD = DCD->getDescribedTemplate()) {
1845           TemplateParameterList *TPL = TD->getTemplateParameters();
1846           auto Index = getDepthAndIndex(D).second;
1847           SearchDefinitions = Index >= TPL->size() || TPL->getParam(Index) != D;
1848         }
1849       }
1850       if (SearchDefinitions)
1851         AcceptableWithinParent =
1852             SemaRef.hasAcceptableDefinition(cast<NamedDecl>(DC), Kind);
1853       else
1854         AcceptableWithinParent =
1855             isAcceptable(SemaRef, cast<NamedDecl>(DC), Kind);
1856     } else if (isa<ParmVarDecl>(D) ||
1857                (isa<FunctionDecl>(DC) && !SemaRef.getLangOpts().CPlusPlus))
1858       AcceptableWithinParent = isAcceptable(SemaRef, cast<NamedDecl>(DC), Kind);
1859     else if (D->isModulePrivate()) {
1860       // A module-private declaration is only acceptable if an enclosing lexical
1861       // parent was merged with another definition in the current module.
1862       AcceptableWithinParent = false;
1863       do {
1864         if (SemaRef.hasMergedDefinitionInCurrentModule(cast<NamedDecl>(DC))) {
1865           AcceptableWithinParent = true;
1866           break;
1867         }
1868         DC = DC->getLexicalParent();
1869       } while (!IsEffectivelyFileContext(DC));
1870     } else {
1871       AcceptableWithinParent =
1872           SemaRef.hasAcceptableDefinition(cast<NamedDecl>(DC), Kind);
1873     }
1874 
1875     if (AcceptableWithinParent && SemaRef.CodeSynthesisContexts.empty() &&
1876         Kind == Sema::AcceptableKind::Visible &&
1877         // FIXME: Do something better in this case.
1878         !SemaRef.getLangOpts().ModulesLocalVisibility) {
1879       // Cache the fact that this declaration is implicitly visible because
1880       // its parent has a visible definition.
1881       D->setVisibleDespiteOwningModule();
1882     }
1883     return AcceptableWithinParent;
1884   }
1885 
1886   if (Kind == Sema::AcceptableKind::Visible)
1887     return false;
1888 
1889   assert(Kind == Sema::AcceptableKind::Reachable &&
1890          "Additional Sema::AcceptableKind?");
1891   return isReachableSlow(SemaRef, D);
1892 }
1893 
1894 bool Sema::isModuleVisible(const Module *M, bool ModulePrivate) {
1895   // The module might be ordinarily visible. For a module-private query, that
1896   // means it is part of the current module.
1897   if (ModulePrivate && isUsableModule(M))
1898     return true;
1899 
1900   // For a query which is not module-private, that means it is in our visible
1901   // module set.
1902   if (!ModulePrivate && VisibleModules.isVisible(M))
1903     return true;
1904 
1905   // Otherwise, it might be visible by virtue of the query being within a
1906   // template instantiation or similar that is permitted to look inside M.
1907 
1908   // Find the extra places where we need to look.
1909   const auto &LookupModules = getLookupModules();
1910   if (LookupModules.empty())
1911     return false;
1912 
1913   // If our lookup set contains the module, it's visible.
1914   if (LookupModules.count(M))
1915     return true;
1916 
1917   // The global module fragments are visible to its corresponding module unit.
1918   // So the global module fragment should be visible if the its corresponding
1919   // module unit is visible.
1920   if (M->isGlobalModule() && LookupModules.count(M->getTopLevelModule()))
1921     return true;
1922 
1923   // For a module-private query, that's everywhere we get to look.
1924   if (ModulePrivate)
1925     return false;
1926 
1927   // Check whether M is transitively exported to an import of the lookup set.
1928   return llvm::any_of(LookupModules, [&](const Module *LookupM) {
1929     return LookupM->isModuleVisible(M);
1930   });
1931 }
1932 
1933 // FIXME: Return false directly if we don't have an interface dependency on the
1934 // translation unit containing D.
1935 bool LookupResult::isReachableSlow(Sema &SemaRef, NamedDecl *D) {
1936   assert(!isVisible(SemaRef, D) && "Shouldn't call the slow case.\n");
1937 
1938   Module *DeclModule = SemaRef.getOwningModule(D);
1939   assert(DeclModule && "hidden decl has no owning module");
1940 
1941   // Entities in header like modules are reachable only if they're visible.
1942   if (DeclModule->isHeaderLikeModule())
1943     return false;
1944 
1945   if (!D->isInAnotherModuleUnit())
1946     return true;
1947 
1948   // [module.reach]/p3:
1949   // A declaration D is reachable from a point P if:
1950   // ...
1951   // - D is not discarded ([module.global.frag]), appears in a translation unit
1952   //   that is reachable from P, and does not appear within a private module
1953   //   fragment.
1954   //
1955   // A declaration that's discarded in the GMF should be module-private.
1956   if (D->isModulePrivate())
1957     return false;
1958 
1959   // [module.reach]/p1
1960   //   A translation unit U is necessarily reachable from a point P if U is a
1961   //   module interface unit on which the translation unit containing P has an
1962   //   interface dependency, or the translation unit containing P imports U, in
1963   //   either case prior to P ([module.import]).
1964   //
1965   // [module.import]/p10
1966   //   A translation unit has an interface dependency on a translation unit U if
1967   //   it contains a declaration (possibly a module-declaration) that imports U
1968   //   or if it has an interface dependency on a translation unit that has an
1969   //   interface dependency on U.
1970   //
1971   // So we could conclude the module unit U is necessarily reachable if:
1972   // (1) The module unit U is module interface unit.
1973   // (2) The current unit has an interface dependency on the module unit U.
1974   //
1975   // Here we only check for the first condition. Since we couldn't see
1976   // DeclModule if it isn't (transitively) imported.
1977   if (DeclModule->getTopLevelModule()->isModuleInterfaceUnit())
1978     return true;
1979 
1980   // [module.reach]/p2
1981   //   Additional translation units on
1982   //   which the point within the program has an interface dependency may be
1983   //   considered reachable, but it is unspecified which are and under what
1984   //   circumstances.
1985   //
1986   // The decision here is to treat all additional tranditional units as
1987   // unreachable.
1988   return false;
1989 }
1990 
1991 bool Sema::isAcceptableSlow(const NamedDecl *D, Sema::AcceptableKind Kind) {
1992   return LookupResult::isAcceptable(*this, const_cast<NamedDecl *>(D), Kind);
1993 }
1994 
1995 bool Sema::shouldLinkPossiblyHiddenDecl(LookupResult &R, const NamedDecl *New) {
1996   // FIXME: If there are both visible and hidden declarations, we need to take
1997   // into account whether redeclaration is possible. Example:
1998   //
1999   // Non-imported module:
2000   //   int f(T);        // #1
2001   // Some TU:
2002   //   static int f(U); // #2, not a redeclaration of #1
2003   //   int f(T);        // #3, finds both, should link with #1 if T != U, but
2004   //                    // with #2 if T == U; neither should be ambiguous.
2005   for (auto *D : R) {
2006     if (isVisible(D))
2007       return true;
2008     assert(D->isExternallyDeclarable() &&
2009            "should not have hidden, non-externally-declarable result here");
2010   }
2011 
2012   // This function is called once "New" is essentially complete, but before a
2013   // previous declaration is attached. We can't query the linkage of "New" in
2014   // general, because attaching the previous declaration can change the
2015   // linkage of New to match the previous declaration.
2016   //
2017   // However, because we've just determined that there is no *visible* prior
2018   // declaration, we can compute the linkage here. There are two possibilities:
2019   //
2020   //  * This is not a redeclaration; it's safe to compute the linkage now.
2021   //
2022   //  * This is a redeclaration of a prior declaration that is externally
2023   //    redeclarable. In that case, the linkage of the declaration is not
2024   //    changed by attaching the prior declaration, because both are externally
2025   //    declarable (and thus ExternalLinkage or VisibleNoLinkage).
2026   //
2027   // FIXME: This is subtle and fragile.
2028   return New->isExternallyDeclarable();
2029 }
2030 
2031 /// Retrieve the visible declaration corresponding to D, if any.
2032 ///
2033 /// This routine determines whether the declaration D is visible in the current
2034 /// module, with the current imports. If not, it checks whether any
2035 /// redeclaration of D is visible, and if so, returns that declaration.
2036 ///
2037 /// \returns D, or a visible previous declaration of D, whichever is more recent
2038 /// and visible. If no declaration of D is visible, returns null.
2039 static NamedDecl *findAcceptableDecl(Sema &SemaRef, NamedDecl *D,
2040                                      unsigned IDNS) {
2041   assert(!LookupResult::isAvailableForLookup(SemaRef, D) && "not in slow case");
2042 
2043   for (auto *RD : D->redecls()) {
2044     // Don't bother with extra checks if we already know this one isn't visible.
2045     if (RD == D)
2046       continue;
2047 
2048     auto ND = cast<NamedDecl>(RD);
2049     // FIXME: This is wrong in the case where the previous declaration is not
2050     // visible in the same scope as D. This needs to be done much more
2051     // carefully.
2052     if (ND->isInIdentifierNamespace(IDNS) &&
2053         LookupResult::isAvailableForLookup(SemaRef, ND))
2054       return ND;
2055   }
2056 
2057   return nullptr;
2058 }
2059 
2060 bool Sema::hasVisibleDeclarationSlow(const NamedDecl *D,
2061                                      llvm::SmallVectorImpl<Module *> *Modules) {
2062   assert(!isVisible(D) && "not in slow case");
2063   return hasAcceptableDeclarationImpl(
2064       *this, D, Modules, [](const NamedDecl *) { return true; },
2065       Sema::AcceptableKind::Visible);
2066 }
2067 
2068 bool Sema::hasReachableDeclarationSlow(
2069     const NamedDecl *D, llvm::SmallVectorImpl<Module *> *Modules) {
2070   assert(!isReachable(D) && "not in slow case");
2071   return hasAcceptableDeclarationImpl(
2072       *this, D, Modules, [](const NamedDecl *) { return true; },
2073       Sema::AcceptableKind::Reachable);
2074 }
2075 
2076 NamedDecl *LookupResult::getAcceptableDeclSlow(NamedDecl *D) const {
2077   if (auto *ND = dyn_cast<NamespaceDecl>(D)) {
2078     // Namespaces are a bit of a special case: we expect there to be a lot of
2079     // redeclarations of some namespaces, all declarations of a namespace are
2080     // essentially interchangeable, all declarations are found by name lookup
2081     // if any is, and namespaces are never looked up during template
2082     // instantiation. So we benefit from caching the check in this case, and
2083     // it is correct to do so.
2084     auto *Key = ND->getCanonicalDecl();
2085     if (auto *Acceptable = getSema().VisibleNamespaceCache.lookup(Key))
2086       return Acceptable;
2087     auto *Acceptable = isVisible(getSema(), Key)
2088                            ? Key
2089                            : findAcceptableDecl(getSema(), Key, IDNS);
2090     if (Acceptable)
2091       getSema().VisibleNamespaceCache.insert(std::make_pair(Key, Acceptable));
2092     return Acceptable;
2093   }
2094 
2095   return findAcceptableDecl(getSema(), D, IDNS);
2096 }
2097 
2098 bool LookupResult::isVisible(Sema &SemaRef, NamedDecl *D) {
2099   // If this declaration is already visible, return it directly.
2100   if (D->isUnconditionallyVisible())
2101     return true;
2102 
2103   // During template instantiation, we can refer to hidden declarations, if
2104   // they were visible in any module along the path of instantiation.
2105   return isAcceptableSlow(SemaRef, D, Sema::AcceptableKind::Visible);
2106 }
2107 
2108 bool LookupResult::isReachable(Sema &SemaRef, NamedDecl *D) {
2109   if (D->isUnconditionallyVisible())
2110     return true;
2111 
2112   return isAcceptableSlow(SemaRef, D, Sema::AcceptableKind::Reachable);
2113 }
2114 
2115 bool LookupResult::isAvailableForLookup(Sema &SemaRef, NamedDecl *ND) {
2116   // We should check the visibility at the callsite already.
2117   if (isVisible(SemaRef, ND))
2118     return true;
2119 
2120   // Deduction guide lives in namespace scope generally, but it is just a
2121   // hint to the compilers. What we actually lookup for is the generated member
2122   // of the corresponding template. So it is sufficient to check the
2123   // reachability of the template decl.
2124   if (auto *DeductionGuide = ND->getDeclName().getCXXDeductionGuideTemplate())
2125     return SemaRef.hasReachableDefinition(DeductionGuide);
2126 
2127   // FIXME: The lookup for allocation function is a standalone process.
2128   // (We can find the logics in Sema::FindAllocationFunctions)
2129   //
2130   // Such structure makes it a problem when we instantiate a template
2131   // declaration using placement allocation function if the placement
2132   // allocation function is invisible.
2133   // (See https://github.com/llvm/llvm-project/issues/59601)
2134   //
2135   // Here we workaround it by making the placement allocation functions
2136   // always acceptable. The downside is that we can't diagnose the direct
2137   // use of the invisible placement allocation functions. (Although such uses
2138   // should be rare).
2139   if (auto *FD = dyn_cast<FunctionDecl>(ND);
2140       FD && FD->isReservedGlobalPlacementOperator())
2141     return true;
2142 
2143   auto *DC = ND->getDeclContext();
2144   // If ND is not visible and it is at namespace scope, it shouldn't be found
2145   // by name lookup.
2146   if (DC->isFileContext())
2147     return false;
2148 
2149   // [module.interface]p7
2150   // Class and enumeration member names can be found by name lookup in any
2151   // context in which a definition of the type is reachable.
2152   //
2153   // FIXME: The current implementation didn't consider about scope. For example,
2154   // ```
2155   // // m.cppm
2156   // export module m;
2157   // enum E1 { e1 };
2158   // // Use.cpp
2159   // import m;
2160   // void test() {
2161   //   auto a = E1::e1; // Error as expected.
2162   //   auto b = e1; // Should be error. namespace-scope name e1 is not visible
2163   // }
2164   // ```
2165   // For the above example, the current implementation would emit error for `a`
2166   // correctly. However, the implementation wouldn't diagnose about `b` now.
2167   // Since we only check the reachability for the parent only.
2168   // See clang/test/CXX/module/module.interface/p7.cpp for example.
2169   if (auto *TD = dyn_cast<TagDecl>(DC))
2170     return SemaRef.hasReachableDefinition(TD);
2171 
2172   return false;
2173 }
2174 
2175 bool Sema::LookupName(LookupResult &R, Scope *S, bool AllowBuiltinCreation,
2176                       bool ForceNoCPlusPlus) {
2177   DeclarationName Name = R.getLookupName();
2178   if (!Name) return false;
2179 
2180   LookupNameKind NameKind = R.getLookupKind();
2181 
2182   if (!getLangOpts().CPlusPlus || ForceNoCPlusPlus) {
2183     // Unqualified name lookup in C/Objective-C is purely lexical, so
2184     // search in the declarations attached to the name.
2185     if (NameKind == Sema::LookupRedeclarationWithLinkage) {
2186       // Find the nearest non-transparent declaration scope.
2187       while (!(S->getFlags() & Scope::DeclScope) ||
2188              (S->getEntity() && S->getEntity()->isTransparentContext()))
2189         S = S->getParent();
2190     }
2191 
2192     // When performing a scope lookup, we want to find local extern decls.
2193     FindLocalExternScope FindLocals(R);
2194 
2195     // Scan up the scope chain looking for a decl that matches this
2196     // identifier that is in the appropriate namespace.  This search
2197     // should not take long, as shadowing of names is uncommon, and
2198     // deep shadowing is extremely uncommon.
2199     bool LeftStartingScope = false;
2200 
2201     for (IdentifierResolver::iterator I = IdResolver.begin(Name),
2202                                    IEnd = IdResolver.end();
2203          I != IEnd; ++I)
2204       if (NamedDecl *D = R.getAcceptableDecl(*I)) {
2205         if (NameKind == LookupRedeclarationWithLinkage) {
2206           // Determine whether this (or a previous) declaration is
2207           // out-of-scope.
2208           if (!LeftStartingScope && !S->isDeclScope(*I))
2209             LeftStartingScope = true;
2210 
2211           // If we found something outside of our starting scope that
2212           // does not have linkage, skip it.
2213           if (LeftStartingScope && !((*I)->hasLinkage())) {
2214             R.setShadowed();
2215             continue;
2216           }
2217         }
2218         else if (NameKind == LookupObjCImplicitSelfParam &&
2219                  !isa<ImplicitParamDecl>(*I))
2220           continue;
2221 
2222         R.addDecl(D);
2223 
2224         // Check whether there are any other declarations with the same name
2225         // and in the same scope.
2226         if (I != IEnd) {
2227           // Find the scope in which this declaration was declared (if it
2228           // actually exists in a Scope).
2229           while (S && !S->isDeclScope(D))
2230             S = S->getParent();
2231 
2232           // If the scope containing the declaration is the translation unit,
2233           // then we'll need to perform our checks based on the matching
2234           // DeclContexts rather than matching scopes.
2235           if (S && isNamespaceOrTranslationUnitScope(S))
2236             S = nullptr;
2237 
2238           // Compute the DeclContext, if we need it.
2239           DeclContext *DC = nullptr;
2240           if (!S)
2241             DC = (*I)->getDeclContext()->getRedeclContext();
2242 
2243           IdentifierResolver::iterator LastI = I;
2244           for (++LastI; LastI != IEnd; ++LastI) {
2245             if (S) {
2246               // Match based on scope.
2247               if (!S->isDeclScope(*LastI))
2248                 break;
2249             } else {
2250               // Match based on DeclContext.
2251               DeclContext *LastDC
2252                 = (*LastI)->getDeclContext()->getRedeclContext();
2253               if (!LastDC->Equals(DC))
2254                 break;
2255             }
2256 
2257             // If the declaration is in the right namespace and visible, add it.
2258             if (NamedDecl *LastD = R.getAcceptableDecl(*LastI))
2259               R.addDecl(LastD);
2260           }
2261 
2262           R.resolveKind();
2263         }
2264 
2265         return true;
2266       }
2267   } else {
2268     // Perform C++ unqualified name lookup.
2269     if (CppLookupName(R, S))
2270       return true;
2271   }
2272 
2273   // If we didn't find a use of this identifier, and if the identifier
2274   // corresponds to a compiler builtin, create the decl object for the builtin
2275   // now, injecting it into translation unit scope, and return it.
2276   if (AllowBuiltinCreation && LookupBuiltin(R))
2277     return true;
2278 
2279   // If we didn't find a use of this identifier, the ExternalSource
2280   // may be able to handle the situation.
2281   // Note: some lookup failures are expected!
2282   // See e.g. R.isForRedeclaration().
2283   return (ExternalSource && ExternalSource->LookupUnqualified(R, S));
2284 }
2285 
2286 /// Perform qualified name lookup in the namespaces nominated by
2287 /// using directives by the given context.
2288 ///
2289 /// C++98 [namespace.qual]p2:
2290 ///   Given X::m (where X is a user-declared namespace), or given \::m
2291 ///   (where X is the global namespace), let S be the set of all
2292 ///   declarations of m in X and in the transitive closure of all
2293 ///   namespaces nominated by using-directives in X and its used
2294 ///   namespaces, except that using-directives are ignored in any
2295 ///   namespace, including X, directly containing one or more
2296 ///   declarations of m. No namespace is searched more than once in
2297 ///   the lookup of a name. If S is the empty set, the program is
2298 ///   ill-formed. Otherwise, if S has exactly one member, or if the
2299 ///   context of the reference is a using-declaration
2300 ///   (namespace.udecl), S is the required set of declarations of
2301 ///   m. Otherwise if the use of m is not one that allows a unique
2302 ///   declaration to be chosen from S, the program is ill-formed.
2303 ///
2304 /// C++98 [namespace.qual]p5:
2305 ///   During the lookup of a qualified namespace member name, if the
2306 ///   lookup finds more than one declaration of the member, and if one
2307 ///   declaration introduces a class name or enumeration name and the
2308 ///   other declarations either introduce the same object, the same
2309 ///   enumerator or a set of functions, the non-type name hides the
2310 ///   class or enumeration name if and only if the declarations are
2311 ///   from the same namespace; otherwise (the declarations are from
2312 ///   different namespaces), the program is ill-formed.
2313 static bool LookupQualifiedNameInUsingDirectives(Sema &S, LookupResult &R,
2314                                                  DeclContext *StartDC) {
2315   assert(StartDC->isFileContext() && "start context is not a file context");
2316 
2317   // We have not yet looked into these namespaces, much less added
2318   // their "using-children" to the queue.
2319   SmallVector<NamespaceDecl*, 8> Queue;
2320 
2321   // We have at least added all these contexts to the queue.
2322   llvm::SmallPtrSet<DeclContext*, 8> Visited;
2323   Visited.insert(StartDC);
2324 
2325   // We have already looked into the initial namespace; seed the queue
2326   // with its using-children.
2327   for (auto *I : StartDC->using_directives()) {
2328     NamespaceDecl *ND = I->getNominatedNamespace()->getFirstDecl();
2329     if (S.isVisible(I) && Visited.insert(ND).second)
2330       Queue.push_back(ND);
2331   }
2332 
2333   // The easiest way to implement the restriction in [namespace.qual]p5
2334   // is to check whether any of the individual results found a tag
2335   // and, if so, to declare an ambiguity if the final result is not
2336   // a tag.
2337   bool FoundTag = false;
2338   bool FoundNonTag = false;
2339 
2340   LookupResult LocalR(LookupResult::Temporary, R);
2341 
2342   bool Found = false;
2343   while (!Queue.empty()) {
2344     NamespaceDecl *ND = Queue.pop_back_val();
2345 
2346     // We go through some convolutions here to avoid copying results
2347     // between LookupResults.
2348     bool UseLocal = !R.empty();
2349     LookupResult &DirectR = UseLocal ? LocalR : R;
2350     bool FoundDirect = LookupDirect(S, DirectR, ND);
2351 
2352     if (FoundDirect) {
2353       // First do any local hiding.
2354       DirectR.resolveKind();
2355 
2356       // If the local result is a tag, remember that.
2357       if (DirectR.isSingleTagDecl())
2358         FoundTag = true;
2359       else
2360         FoundNonTag = true;
2361 
2362       // Append the local results to the total results if necessary.
2363       if (UseLocal) {
2364         R.addAllDecls(LocalR);
2365         LocalR.clear();
2366       }
2367     }
2368 
2369     // If we find names in this namespace, ignore its using directives.
2370     if (FoundDirect) {
2371       Found = true;
2372       continue;
2373     }
2374 
2375     for (auto *I : ND->using_directives()) {
2376       NamespaceDecl *Nom = I->getNominatedNamespace();
2377       if (S.isVisible(I) && Visited.insert(Nom).second)
2378         Queue.push_back(Nom);
2379     }
2380   }
2381 
2382   if (Found) {
2383     if (FoundTag && FoundNonTag)
2384       R.setAmbiguousQualifiedTagHiding();
2385     else
2386       R.resolveKind();
2387   }
2388 
2389   return Found;
2390 }
2391 
2392 bool Sema::LookupQualifiedName(LookupResult &R, DeclContext *LookupCtx,
2393                                bool InUnqualifiedLookup) {
2394   assert(LookupCtx && "Sema::LookupQualifiedName requires a lookup context");
2395 
2396   if (!R.getLookupName())
2397     return false;
2398 
2399   // Make sure that the declaration context is complete.
2400   assert((!isa<TagDecl>(LookupCtx) ||
2401           LookupCtx->isDependentContext() ||
2402           cast<TagDecl>(LookupCtx)->isCompleteDefinition() ||
2403           cast<TagDecl>(LookupCtx)->isBeingDefined()) &&
2404          "Declaration context must already be complete!");
2405 
2406   struct QualifiedLookupInScope {
2407     bool oldVal;
2408     DeclContext *Context;
2409     // Set flag in DeclContext informing debugger that we're looking for qualified name
2410     QualifiedLookupInScope(DeclContext *ctx)
2411         : oldVal(ctx->shouldUseQualifiedLookup()), Context(ctx) {
2412       ctx->setUseQualifiedLookup();
2413     }
2414     ~QualifiedLookupInScope() {
2415       Context->setUseQualifiedLookup(oldVal);
2416     }
2417   } QL(LookupCtx);
2418 
2419   CXXRecordDecl *LookupRec = dyn_cast<CXXRecordDecl>(LookupCtx);
2420   // FIXME: Per [temp.dep.general]p2, an unqualified name is also dependent
2421   // if it's a dependent conversion-function-id or operator= where the current
2422   // class is a templated entity. This should be handled in LookupName.
2423   if (!InUnqualifiedLookup && !R.isForRedeclaration()) {
2424     // C++23 [temp.dep.type]p5:
2425     //   A qualified name is dependent if
2426     //   - it is a conversion-function-id whose conversion-type-id
2427     //     is dependent, or
2428     //   - [...]
2429     //   - its lookup context is the current instantiation and it
2430     //     is operator=, or
2431     //   - [...]
2432     if (DeclarationName Name = R.getLookupName();
2433         Name.getNameKind() == DeclarationName::CXXConversionFunctionName &&
2434         Name.getCXXNameType()->isDependentType()) {
2435       R.setNotFoundInCurrentInstantiation();
2436       return false;
2437     }
2438   }
2439 
2440   if (LookupDirect(*this, R, LookupCtx)) {
2441     R.resolveKind();
2442     if (LookupRec)
2443       R.setNamingClass(LookupRec);
2444     return true;
2445   }
2446 
2447   // Don't descend into implied contexts for redeclarations.
2448   // C++98 [namespace.qual]p6:
2449   //   In a declaration for a namespace member in which the
2450   //   declarator-id is a qualified-id, given that the qualified-id
2451   //   for the namespace member has the form
2452   //     nested-name-specifier unqualified-id
2453   //   the unqualified-id shall name a member of the namespace
2454   //   designated by the nested-name-specifier.
2455   // See also [class.mfct]p5 and [class.static.data]p2.
2456   if (R.isForRedeclaration())
2457     return false;
2458 
2459   // If this is a namespace, look it up in the implied namespaces.
2460   if (LookupCtx->isFileContext())
2461     return LookupQualifiedNameInUsingDirectives(*this, R, LookupCtx);
2462 
2463   // If this isn't a C++ class, we aren't allowed to look into base
2464   // classes, we're done.
2465   if (!LookupRec || !LookupRec->getDefinition())
2466     return false;
2467 
2468   // We're done for lookups that can never succeed for C++ classes.
2469   if (R.getLookupKind() == LookupOperatorName ||
2470       R.getLookupKind() == LookupNamespaceName ||
2471       R.getLookupKind() == LookupObjCProtocolName ||
2472       R.getLookupKind() == LookupLabel)
2473     return false;
2474 
2475   // If we're performing qualified name lookup into a dependent class,
2476   // then we are actually looking into a current instantiation. If we have any
2477   // dependent base classes, then we either have to delay lookup until
2478   // template instantiation time (at which point all bases will be available)
2479   // or we have to fail.
2480   if (!InUnqualifiedLookup && LookupRec->isDependentContext() &&
2481       LookupRec->hasAnyDependentBases()) {
2482     R.setNotFoundInCurrentInstantiation();
2483     return false;
2484   }
2485 
2486   // Perform lookup into our base classes.
2487 
2488   DeclarationName Name = R.getLookupName();
2489   unsigned IDNS = R.getIdentifierNamespace();
2490 
2491   // Look for this member in our base classes.
2492   auto BaseCallback = [Name, IDNS](const CXXBaseSpecifier *Specifier,
2493                                    CXXBasePath &Path) -> bool {
2494     CXXRecordDecl *BaseRecord = Specifier->getType()->getAsCXXRecordDecl();
2495     // Drop leading non-matching lookup results from the declaration list so
2496     // we don't need to consider them again below.
2497     for (Path.Decls = BaseRecord->lookup(Name).begin();
2498          Path.Decls != Path.Decls.end(); ++Path.Decls) {
2499       if ((*Path.Decls)->isInIdentifierNamespace(IDNS))
2500         return true;
2501     }
2502     return false;
2503   };
2504 
2505   CXXBasePaths Paths;
2506   Paths.setOrigin(LookupRec);
2507   if (!LookupRec->lookupInBases(BaseCallback, Paths))
2508     return false;
2509 
2510   R.setNamingClass(LookupRec);
2511 
2512   // C++ [class.member.lookup]p2:
2513   //   [...] If the resulting set of declarations are not all from
2514   //   sub-objects of the same type, or the set has a nonstatic member
2515   //   and includes members from distinct sub-objects, there is an
2516   //   ambiguity and the program is ill-formed. Otherwise that set is
2517   //   the result of the lookup.
2518   QualType SubobjectType;
2519   int SubobjectNumber = 0;
2520   AccessSpecifier SubobjectAccess = AS_none;
2521 
2522   // Check whether the given lookup result contains only static members.
2523   auto HasOnlyStaticMembers = [&](DeclContext::lookup_iterator Result) {
2524     for (DeclContext::lookup_iterator I = Result, E = I.end(); I != E; ++I)
2525       if ((*I)->isInIdentifierNamespace(IDNS) && (*I)->isCXXInstanceMember())
2526         return false;
2527     return true;
2528   };
2529 
2530   bool TemplateNameLookup = R.isTemplateNameLookup();
2531 
2532   // Determine whether two sets of members contain the same members, as
2533   // required by C++ [class.member.lookup]p6.
2534   auto HasSameDeclarations = [&](DeclContext::lookup_iterator A,
2535                                  DeclContext::lookup_iterator B) {
2536     using Iterator = DeclContextLookupResult::iterator;
2537     using Result = const void *;
2538 
2539     auto Next = [&](Iterator &It, Iterator End) -> Result {
2540       while (It != End) {
2541         NamedDecl *ND = *It++;
2542         if (!ND->isInIdentifierNamespace(IDNS))
2543           continue;
2544 
2545         // C++ [temp.local]p3:
2546         //   A lookup that finds an injected-class-name (10.2) can result in
2547         //   an ambiguity in certain cases (for example, if it is found in
2548         //   more than one base class). If all of the injected-class-names
2549         //   that are found refer to specializations of the same class
2550         //   template, and if the name is used as a template-name, the
2551         //   reference refers to the class template itself and not a
2552         //   specialization thereof, and is not ambiguous.
2553         if (TemplateNameLookup)
2554           if (auto *TD = getAsTemplateNameDecl(ND))
2555             ND = TD;
2556 
2557         // C++ [class.member.lookup]p3:
2558         //   type declarations (including injected-class-names) are replaced by
2559         //   the types they designate
2560         if (const TypeDecl *TD = dyn_cast<TypeDecl>(ND->getUnderlyingDecl())) {
2561           QualType T = Context.getTypeDeclType(TD);
2562           return T.getCanonicalType().getAsOpaquePtr();
2563         }
2564 
2565         return ND->getUnderlyingDecl()->getCanonicalDecl();
2566       }
2567       return nullptr;
2568     };
2569 
2570     // We'll often find the declarations are in the same order. Handle this
2571     // case (and the special case of only one declaration) efficiently.
2572     Iterator AIt = A, BIt = B, AEnd, BEnd;
2573     while (true) {
2574       Result AResult = Next(AIt, AEnd);
2575       Result BResult = Next(BIt, BEnd);
2576       if (!AResult && !BResult)
2577         return true;
2578       if (!AResult || !BResult)
2579         return false;
2580       if (AResult != BResult) {
2581         // Found a mismatch; carefully check both lists, accounting for the
2582         // possibility of declarations appearing more than once.
2583         llvm::SmallDenseMap<Result, bool, 32> AResults;
2584         for (; AResult; AResult = Next(AIt, AEnd))
2585           AResults.insert({AResult, /*FoundInB*/false});
2586         unsigned Found = 0;
2587         for (; BResult; BResult = Next(BIt, BEnd)) {
2588           auto It = AResults.find(BResult);
2589           if (It == AResults.end())
2590             return false;
2591           if (!It->second) {
2592             It->second = true;
2593             ++Found;
2594           }
2595         }
2596         return AResults.size() == Found;
2597       }
2598     }
2599   };
2600 
2601   for (CXXBasePaths::paths_iterator Path = Paths.begin(), PathEnd = Paths.end();
2602        Path != PathEnd; ++Path) {
2603     const CXXBasePathElement &PathElement = Path->back();
2604 
2605     // Pick the best (i.e. most permissive i.e. numerically lowest) access
2606     // across all paths.
2607     SubobjectAccess = std::min(SubobjectAccess, Path->Access);
2608 
2609     // Determine whether we're looking at a distinct sub-object or not.
2610     if (SubobjectType.isNull()) {
2611       // This is the first subobject we've looked at. Record its type.
2612       SubobjectType = Context.getCanonicalType(PathElement.Base->getType());
2613       SubobjectNumber = PathElement.SubobjectNumber;
2614       continue;
2615     }
2616 
2617     if (SubobjectType !=
2618         Context.getCanonicalType(PathElement.Base->getType())) {
2619       // We found members of the given name in two subobjects of
2620       // different types. If the declaration sets aren't the same, this
2621       // lookup is ambiguous.
2622       //
2623       // FIXME: The language rule says that this applies irrespective of
2624       // whether the sets contain only static members.
2625       if (HasOnlyStaticMembers(Path->Decls) &&
2626           HasSameDeclarations(Paths.begin()->Decls, Path->Decls))
2627         continue;
2628 
2629       R.setAmbiguousBaseSubobjectTypes(Paths);
2630       return true;
2631     }
2632 
2633     // FIXME: This language rule no longer exists. Checking for ambiguous base
2634     // subobjects should be done as part of formation of a class member access
2635     // expression (when converting the object parameter to the member's type).
2636     if (SubobjectNumber != PathElement.SubobjectNumber) {
2637       // We have a different subobject of the same type.
2638 
2639       // C++ [class.member.lookup]p5:
2640       //   A static member, a nested type or an enumerator defined in
2641       //   a base class T can unambiguously be found even if an object
2642       //   has more than one base class subobject of type T.
2643       if (HasOnlyStaticMembers(Path->Decls))
2644         continue;
2645 
2646       // We have found a nonstatic member name in multiple, distinct
2647       // subobjects. Name lookup is ambiguous.
2648       R.setAmbiguousBaseSubobjects(Paths);
2649       return true;
2650     }
2651   }
2652 
2653   // Lookup in a base class succeeded; return these results.
2654 
2655   for (DeclContext::lookup_iterator I = Paths.front().Decls, E = I.end();
2656        I != E; ++I) {
2657     AccessSpecifier AS = CXXRecordDecl::MergeAccess(SubobjectAccess,
2658                                                     (*I)->getAccess());
2659     if (NamedDecl *ND = R.getAcceptableDecl(*I))
2660       R.addDecl(ND, AS);
2661   }
2662   R.resolveKind();
2663   return true;
2664 }
2665 
2666 bool Sema::LookupQualifiedName(LookupResult &R, DeclContext *LookupCtx,
2667                                CXXScopeSpec &SS) {
2668   auto *NNS = SS.getScopeRep();
2669   if (NNS && NNS->getKind() == NestedNameSpecifier::Super)
2670     return LookupInSuper(R, NNS->getAsRecordDecl());
2671   else
2672 
2673     return LookupQualifiedName(R, LookupCtx);
2674 }
2675 
2676 bool Sema::LookupParsedName(LookupResult &R, Scope *S, CXXScopeSpec *SS,
2677                             QualType ObjectType, bool AllowBuiltinCreation,
2678                             bool EnteringContext) {
2679   // When the scope specifier is invalid, don't even look for anything.
2680   if (SS && SS->isInvalid())
2681     return false;
2682 
2683   // Determine where to perform name lookup
2684   DeclContext *DC = nullptr;
2685   bool IsDependent = false;
2686   if (!ObjectType.isNull()) {
2687     // This nested-name-specifier occurs in a member access expression, e.g.,
2688     // x->B::f, and we are looking into the type of the object.
2689     assert((!SS || SS->isEmpty()) &&
2690            "ObjectType and scope specifier cannot coexist");
2691     DC = computeDeclContext(ObjectType);
2692     IsDependent = !DC && ObjectType->isDependentType();
2693     assert(((!DC && ObjectType->isDependentType()) ||
2694             !ObjectType->isIncompleteType() || !ObjectType->getAs<TagType>() ||
2695             ObjectType->castAs<TagType>()->isBeingDefined()) &&
2696            "Caller should have completed object type");
2697   } else if (SS && SS->isNotEmpty()) {
2698     // This nested-name-specifier occurs after another nested-name-specifier,
2699     // so long into the context associated with the prior nested-name-specifier.
2700     if ((DC = computeDeclContext(*SS, EnteringContext))) {
2701       // The declaration context must be complete.
2702       if (!DC->isDependentContext() && RequireCompleteDeclContext(*SS, DC))
2703         return false;
2704       R.setContextRange(SS->getRange());
2705       // FIXME: '__super' lookup semantics could be implemented by a
2706       // LookupResult::isSuperLookup flag which skips the initial search of
2707       // the lookup context in LookupQualified.
2708       if (NestedNameSpecifier *NNS = SS->getScopeRep();
2709           NNS->getKind() == NestedNameSpecifier::Super)
2710         return LookupInSuper(R, NNS->getAsRecordDecl());
2711     }
2712     IsDependent = !DC && isDependentScopeSpecifier(*SS);
2713   } else {
2714     // Perform unqualified name lookup starting in the given scope.
2715     return LookupName(R, S, AllowBuiltinCreation);
2716   }
2717 
2718   // If we were able to compute a declaration context, perform qualified name
2719   // lookup in that context.
2720   if (DC)
2721     return LookupQualifiedName(R, DC);
2722   else if (IsDependent)
2723     // We could not resolve the scope specified to a specific declaration
2724     // context, which means that SS refers to an unknown specialization.
2725     // Name lookup can't find anything in this case.
2726     R.setNotFoundInCurrentInstantiation();
2727   return false;
2728 }
2729 
2730 bool Sema::LookupInSuper(LookupResult &R, CXXRecordDecl *Class) {
2731   // The access-control rules we use here are essentially the rules for
2732   // doing a lookup in Class that just magically skipped the direct
2733   // members of Class itself.  That is, the naming class is Class, and the
2734   // access includes the access of the base.
2735   for (const auto &BaseSpec : Class->bases()) {
2736     CXXRecordDecl *RD = cast<CXXRecordDecl>(
2737         BaseSpec.getType()->castAs<RecordType>()->getDecl());
2738     LookupResult Result(*this, R.getLookupNameInfo(), R.getLookupKind());
2739     Result.setBaseObjectType(Context.getRecordType(Class));
2740     LookupQualifiedName(Result, RD);
2741 
2742     // Copy the lookup results into the target, merging the base's access into
2743     // the path access.
2744     for (auto I = Result.begin(), E = Result.end(); I != E; ++I) {
2745       R.addDecl(I.getDecl(),
2746                 CXXRecordDecl::MergeAccess(BaseSpec.getAccessSpecifier(),
2747                                            I.getAccess()));
2748     }
2749 
2750     Result.suppressDiagnostics();
2751   }
2752 
2753   R.resolveKind();
2754   R.setNamingClass(Class);
2755 
2756   return !R.empty();
2757 }
2758 
2759 void Sema::DiagnoseAmbiguousLookup(LookupResult &Result) {
2760   assert(Result.isAmbiguous() && "Lookup result must be ambiguous");
2761 
2762   DeclarationName Name = Result.getLookupName();
2763   SourceLocation NameLoc = Result.getNameLoc();
2764   SourceRange LookupRange = Result.getContextRange();
2765 
2766   switch (Result.getAmbiguityKind()) {
2767   case LookupResult::AmbiguousBaseSubobjects: {
2768     CXXBasePaths *Paths = Result.getBasePaths();
2769     QualType SubobjectType = Paths->front().back().Base->getType();
2770     Diag(NameLoc, diag::err_ambiguous_member_multiple_subobjects)
2771       << Name << SubobjectType << getAmbiguousPathsDisplayString(*Paths)
2772       << LookupRange;
2773 
2774     DeclContext::lookup_iterator Found = Paths->front().Decls;
2775     while (isa<CXXMethodDecl>(*Found) &&
2776            cast<CXXMethodDecl>(*Found)->isStatic())
2777       ++Found;
2778 
2779     Diag((*Found)->getLocation(), diag::note_ambiguous_member_found);
2780     break;
2781   }
2782 
2783   case LookupResult::AmbiguousBaseSubobjectTypes: {
2784     Diag(NameLoc, diag::err_ambiguous_member_multiple_subobject_types)
2785       << Name << LookupRange;
2786 
2787     CXXBasePaths *Paths = Result.getBasePaths();
2788     std::set<const NamedDecl *> DeclsPrinted;
2789     for (CXXBasePaths::paths_iterator Path = Paths->begin(),
2790                                       PathEnd = Paths->end();
2791          Path != PathEnd; ++Path) {
2792       const NamedDecl *D = *Path->Decls;
2793       if (!D->isInIdentifierNamespace(Result.getIdentifierNamespace()))
2794         continue;
2795       if (DeclsPrinted.insert(D).second) {
2796         if (const auto *TD = dyn_cast<TypedefNameDecl>(D->getUnderlyingDecl()))
2797           Diag(D->getLocation(), diag::note_ambiguous_member_type_found)
2798               << TD->getUnderlyingType();
2799         else if (const auto *TD = dyn_cast<TypeDecl>(D->getUnderlyingDecl()))
2800           Diag(D->getLocation(), diag::note_ambiguous_member_type_found)
2801               << Context.getTypeDeclType(TD);
2802         else
2803           Diag(D->getLocation(), diag::note_ambiguous_member_found);
2804       }
2805     }
2806     break;
2807   }
2808 
2809   case LookupResult::AmbiguousTagHiding: {
2810     Diag(NameLoc, diag::err_ambiguous_tag_hiding) << Name << LookupRange;
2811 
2812     llvm::SmallPtrSet<NamedDecl*, 8> TagDecls;
2813 
2814     for (auto *D : Result)
2815       if (TagDecl *TD = dyn_cast<TagDecl>(D)) {
2816         TagDecls.insert(TD);
2817         Diag(TD->getLocation(), diag::note_hidden_tag);
2818       }
2819 
2820     for (auto *D : Result)
2821       if (!isa<TagDecl>(D))
2822         Diag(D->getLocation(), diag::note_hiding_object);
2823 
2824     // For recovery purposes, go ahead and implement the hiding.
2825     LookupResult::Filter F = Result.makeFilter();
2826     while (F.hasNext()) {
2827       if (TagDecls.count(F.next()))
2828         F.erase();
2829     }
2830     F.done();
2831     break;
2832   }
2833 
2834   case LookupResult::AmbiguousReferenceToPlaceholderVariable: {
2835     Diag(NameLoc, diag::err_using_placeholder_variable) << Name << LookupRange;
2836     DeclContext *DC = nullptr;
2837     for (auto *D : Result) {
2838       Diag(D->getLocation(), diag::note_reference_placeholder) << D;
2839       if (DC != nullptr && DC != D->getDeclContext())
2840         break;
2841       DC = D->getDeclContext();
2842     }
2843     break;
2844   }
2845 
2846   case LookupResult::AmbiguousReference: {
2847     Diag(NameLoc, diag::err_ambiguous_reference) << Name << LookupRange;
2848 
2849     for (auto *D : Result)
2850       Diag(D->getLocation(), diag::note_ambiguous_candidate) << D;
2851     break;
2852   }
2853   }
2854 }
2855 
2856 namespace {
2857   struct AssociatedLookup {
2858     AssociatedLookup(Sema &S, SourceLocation InstantiationLoc,
2859                      Sema::AssociatedNamespaceSet &Namespaces,
2860                      Sema::AssociatedClassSet &Classes)
2861       : S(S), Namespaces(Namespaces), Classes(Classes),
2862         InstantiationLoc(InstantiationLoc) {
2863     }
2864 
2865     bool addClassTransitive(CXXRecordDecl *RD) {
2866       Classes.insert(RD);
2867       return ClassesTransitive.insert(RD);
2868     }
2869 
2870     Sema &S;
2871     Sema::AssociatedNamespaceSet &Namespaces;
2872     Sema::AssociatedClassSet &Classes;
2873     SourceLocation InstantiationLoc;
2874 
2875   private:
2876     Sema::AssociatedClassSet ClassesTransitive;
2877   };
2878 } // end anonymous namespace
2879 
2880 static void
2881 addAssociatedClassesAndNamespaces(AssociatedLookup &Result, QualType T);
2882 
2883 // Given the declaration context \param Ctx of a class, class template or
2884 // enumeration, add the associated namespaces to \param Namespaces as described
2885 // in [basic.lookup.argdep]p2.
2886 static void CollectEnclosingNamespace(Sema::AssociatedNamespaceSet &Namespaces,
2887                                       DeclContext *Ctx) {
2888   // The exact wording has been changed in C++14 as a result of
2889   // CWG 1691 (see also CWG 1690 and CWG 1692). We apply it unconditionally
2890   // to all language versions since it is possible to return a local type
2891   // from a lambda in C++11.
2892   //
2893   // C++14 [basic.lookup.argdep]p2:
2894   //   If T is a class type [...]. Its associated namespaces are the innermost
2895   //   enclosing namespaces of its associated classes. [...]
2896   //
2897   //   If T is an enumeration type, its associated namespace is the innermost
2898   //   enclosing namespace of its declaration. [...]
2899 
2900   // We additionally skip inline namespaces. The innermost non-inline namespace
2901   // contains all names of all its nested inline namespaces anyway, so we can
2902   // replace the entire inline namespace tree with its root.
2903   while (!Ctx->isFileContext() || Ctx->isInlineNamespace())
2904     Ctx = Ctx->getParent();
2905 
2906   Namespaces.insert(Ctx->getPrimaryContext());
2907 }
2908 
2909 // Add the associated classes and namespaces for argument-dependent
2910 // lookup that involves a template argument (C++ [basic.lookup.argdep]p2).
2911 static void
2912 addAssociatedClassesAndNamespaces(AssociatedLookup &Result,
2913                                   const TemplateArgument &Arg) {
2914   // C++ [basic.lookup.argdep]p2, last bullet:
2915   //   -- [...] ;
2916   switch (Arg.getKind()) {
2917     case TemplateArgument::Null:
2918       break;
2919 
2920     case TemplateArgument::Type:
2921       // [...] the namespaces and classes associated with the types of the
2922       // template arguments provided for template type parameters (excluding
2923       // template template parameters)
2924       addAssociatedClassesAndNamespaces(Result, Arg.getAsType());
2925       break;
2926 
2927     case TemplateArgument::Template:
2928     case TemplateArgument::TemplateExpansion: {
2929       // [...] the namespaces in which any template template arguments are
2930       // defined; and the classes in which any member templates used as
2931       // template template arguments are defined.
2932       TemplateName Template = Arg.getAsTemplateOrTemplatePattern();
2933       if (ClassTemplateDecl *ClassTemplate
2934                  = dyn_cast<ClassTemplateDecl>(Template.getAsTemplateDecl())) {
2935         DeclContext *Ctx = ClassTemplate->getDeclContext();
2936         if (CXXRecordDecl *EnclosingClass = dyn_cast<CXXRecordDecl>(Ctx))
2937           Result.Classes.insert(EnclosingClass);
2938         // Add the associated namespace for this class.
2939         CollectEnclosingNamespace(Result.Namespaces, Ctx);
2940       }
2941       break;
2942     }
2943 
2944     case TemplateArgument::Declaration:
2945     case TemplateArgument::Integral:
2946     case TemplateArgument::Expression:
2947     case TemplateArgument::NullPtr:
2948     case TemplateArgument::StructuralValue:
2949       // [Note: non-type template arguments do not contribute to the set of
2950       //  associated namespaces. ]
2951       break;
2952 
2953     case TemplateArgument::Pack:
2954       for (const auto &P : Arg.pack_elements())
2955         addAssociatedClassesAndNamespaces(Result, P);
2956       break;
2957   }
2958 }
2959 
2960 // Add the associated classes and namespaces for argument-dependent lookup
2961 // with an argument of class type (C++ [basic.lookup.argdep]p2).
2962 static void
2963 addAssociatedClassesAndNamespaces(AssociatedLookup &Result,
2964                                   CXXRecordDecl *Class) {
2965 
2966   // Just silently ignore anything whose name is __va_list_tag.
2967   if (Class->getDeclName() == Result.S.VAListTagName)
2968     return;
2969 
2970   // C++ [basic.lookup.argdep]p2:
2971   //   [...]
2972   //     -- If T is a class type (including unions), its associated
2973   //        classes are: the class itself; the class of which it is a
2974   //        member, if any; and its direct and indirect base classes.
2975   //        Its associated namespaces are the innermost enclosing
2976   //        namespaces of its associated classes.
2977 
2978   // Add the class of which it is a member, if any.
2979   DeclContext *Ctx = Class->getDeclContext();
2980   if (CXXRecordDecl *EnclosingClass = dyn_cast<CXXRecordDecl>(Ctx))
2981     Result.Classes.insert(EnclosingClass);
2982 
2983   // Add the associated namespace for this class.
2984   CollectEnclosingNamespace(Result.Namespaces, Ctx);
2985 
2986   // -- If T is a template-id, its associated namespaces and classes are
2987   //    the namespace in which the template is defined; for member
2988   //    templates, the member template's class; the namespaces and classes
2989   //    associated with the types of the template arguments provided for
2990   //    template type parameters (excluding template template parameters); the
2991   //    namespaces in which any template template arguments are defined; and
2992   //    the classes in which any member templates used as template template
2993   //    arguments are defined. [Note: non-type template arguments do not
2994   //    contribute to the set of associated namespaces. ]
2995   if (ClassTemplateSpecializationDecl *Spec
2996         = dyn_cast<ClassTemplateSpecializationDecl>(Class)) {
2997     DeclContext *Ctx = Spec->getSpecializedTemplate()->getDeclContext();
2998     if (CXXRecordDecl *EnclosingClass = dyn_cast<CXXRecordDecl>(Ctx))
2999       Result.Classes.insert(EnclosingClass);
3000     // Add the associated namespace for this class.
3001     CollectEnclosingNamespace(Result.Namespaces, Ctx);
3002 
3003     const TemplateArgumentList &TemplateArgs = Spec->getTemplateArgs();
3004     for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
3005       addAssociatedClassesAndNamespaces(Result, TemplateArgs[I]);
3006   }
3007 
3008   // Add the class itself. If we've already transitively visited this class,
3009   // we don't need to visit base classes.
3010   if (!Result.addClassTransitive(Class))
3011     return;
3012 
3013   // Only recurse into base classes for complete types.
3014   if (!Result.S.isCompleteType(Result.InstantiationLoc,
3015                                Result.S.Context.getRecordType(Class)))
3016     return;
3017 
3018   // Add direct and indirect base classes along with their associated
3019   // namespaces.
3020   SmallVector<CXXRecordDecl *, 32> Bases;
3021   Bases.push_back(Class);
3022   while (!Bases.empty()) {
3023     // Pop this class off the stack.
3024     Class = Bases.pop_back_val();
3025 
3026     // Visit the base classes.
3027     for (const auto &Base : Class->bases()) {
3028       const RecordType *BaseType = Base.getType()->getAs<RecordType>();
3029       // In dependent contexts, we do ADL twice, and the first time around,
3030       // the base type might be a dependent TemplateSpecializationType, or a
3031       // TemplateTypeParmType. If that happens, simply ignore it.
3032       // FIXME: If we want to support export, we probably need to add the
3033       // namespace of the template in a TemplateSpecializationType, or even
3034       // the classes and namespaces of known non-dependent arguments.
3035       if (!BaseType)
3036         continue;
3037       CXXRecordDecl *BaseDecl = cast<CXXRecordDecl>(BaseType->getDecl());
3038       if (Result.addClassTransitive(BaseDecl)) {
3039         // Find the associated namespace for this base class.
3040         DeclContext *BaseCtx = BaseDecl->getDeclContext();
3041         CollectEnclosingNamespace(Result.Namespaces, BaseCtx);
3042 
3043         // Make sure we visit the bases of this base class.
3044         if (BaseDecl->bases_begin() != BaseDecl->bases_end())
3045           Bases.push_back(BaseDecl);
3046       }
3047     }
3048   }
3049 }
3050 
3051 // Add the associated classes and namespaces for
3052 // argument-dependent lookup with an argument of type T
3053 // (C++ [basic.lookup.koenig]p2).
3054 static void
3055 addAssociatedClassesAndNamespaces(AssociatedLookup &Result, QualType Ty) {
3056   // C++ [basic.lookup.koenig]p2:
3057   //
3058   //   For each argument type T in the function call, there is a set
3059   //   of zero or more associated namespaces and a set of zero or more
3060   //   associated classes to be considered. The sets of namespaces and
3061   //   classes is determined entirely by the types of the function
3062   //   arguments (and the namespace of any template template
3063   //   argument). Typedef names and using-declarations used to specify
3064   //   the types do not contribute to this set. The sets of namespaces
3065   //   and classes are determined in the following way:
3066 
3067   SmallVector<const Type *, 16> Queue;
3068   const Type *T = Ty->getCanonicalTypeInternal().getTypePtr();
3069 
3070   while (true) {
3071     switch (T->getTypeClass()) {
3072 
3073 #define TYPE(Class, Base)
3074 #define DEPENDENT_TYPE(Class, Base) case Type::Class:
3075 #define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
3076 #define NON_CANONICAL_UNLESS_DEPENDENT_TYPE(Class, Base) case Type::Class:
3077 #define ABSTRACT_TYPE(Class, Base)
3078 #include "clang/AST/TypeNodes.inc"
3079       // T is canonical.  We can also ignore dependent types because
3080       // we don't need to do ADL at the definition point, but if we
3081       // wanted to implement template export (or if we find some other
3082       // use for associated classes and namespaces...) this would be
3083       // wrong.
3084       break;
3085 
3086     //    -- If T is a pointer to U or an array of U, its associated
3087     //       namespaces and classes are those associated with U.
3088     case Type::Pointer:
3089       T = cast<PointerType>(T)->getPointeeType().getTypePtr();
3090       continue;
3091     case Type::ConstantArray:
3092     case Type::IncompleteArray:
3093     case Type::VariableArray:
3094       T = cast<ArrayType>(T)->getElementType().getTypePtr();
3095       continue;
3096 
3097     //     -- If T is a fundamental type, its associated sets of
3098     //        namespaces and classes are both empty.
3099     case Type::Builtin:
3100       break;
3101 
3102     //     -- If T is a class type (including unions), its associated
3103     //        classes are: the class itself; the class of which it is
3104     //        a member, if any; and its direct and indirect base classes.
3105     //        Its associated namespaces are the innermost enclosing
3106     //        namespaces of its associated classes.
3107     case Type::Record: {
3108       CXXRecordDecl *Class =
3109           cast<CXXRecordDecl>(cast<RecordType>(T)->getDecl());
3110       addAssociatedClassesAndNamespaces(Result, Class);
3111       break;
3112     }
3113 
3114     //     -- If T is an enumeration type, its associated namespace
3115     //        is the innermost enclosing namespace of its declaration.
3116     //        If it is a class member, its associated class is the
3117     //        member’s class; else it has no associated class.
3118     case Type::Enum: {
3119       EnumDecl *Enum = cast<EnumType>(T)->getDecl();
3120 
3121       DeclContext *Ctx = Enum->getDeclContext();
3122       if (CXXRecordDecl *EnclosingClass = dyn_cast<CXXRecordDecl>(Ctx))
3123         Result.Classes.insert(EnclosingClass);
3124 
3125       // Add the associated namespace for this enumeration.
3126       CollectEnclosingNamespace(Result.Namespaces, Ctx);
3127 
3128       break;
3129     }
3130 
3131     //     -- If T is a function type, its associated namespaces and
3132     //        classes are those associated with the function parameter
3133     //        types and those associated with the return type.
3134     case Type::FunctionProto: {
3135       const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
3136       for (const auto &Arg : Proto->param_types())
3137         Queue.push_back(Arg.getTypePtr());
3138       // fallthrough
3139       [[fallthrough]];
3140     }
3141     case Type::FunctionNoProto: {
3142       const FunctionType *FnType = cast<FunctionType>(T);
3143       T = FnType->getReturnType().getTypePtr();
3144       continue;
3145     }
3146 
3147     //     -- If T is a pointer to a member function of a class X, its
3148     //        associated namespaces and classes are those associated
3149     //        with the function parameter types and return type,
3150     //        together with those associated with X.
3151     //
3152     //     -- If T is a pointer to a data member of class X, its
3153     //        associated namespaces and classes are those associated
3154     //        with the member type together with those associated with
3155     //        X.
3156     case Type::MemberPointer: {
3157       const MemberPointerType *MemberPtr = cast<MemberPointerType>(T);
3158 
3159       // Queue up the class type into which this points.
3160       Queue.push_back(MemberPtr->getClass());
3161 
3162       // And directly continue with the pointee type.
3163       T = MemberPtr->getPointeeType().getTypePtr();
3164       continue;
3165     }
3166 
3167     // As an extension, treat this like a normal pointer.
3168     case Type::BlockPointer:
3169       T = cast<BlockPointerType>(T)->getPointeeType().getTypePtr();
3170       continue;
3171 
3172     // References aren't covered by the standard, but that's such an
3173     // obvious defect that we cover them anyway.
3174     case Type::LValueReference:
3175     case Type::RValueReference:
3176       T = cast<ReferenceType>(T)->getPointeeType().getTypePtr();
3177       continue;
3178 
3179     // These are fundamental types.
3180     case Type::Vector:
3181     case Type::ExtVector:
3182     case Type::ConstantMatrix:
3183     case Type::Complex:
3184     case Type::BitInt:
3185       break;
3186 
3187     // Non-deduced auto types only get here for error cases.
3188     case Type::Auto:
3189     case Type::DeducedTemplateSpecialization:
3190       break;
3191 
3192     // If T is an Objective-C object or interface type, or a pointer to an
3193     // object or interface type, the associated namespace is the global
3194     // namespace.
3195     case Type::ObjCObject:
3196     case Type::ObjCInterface:
3197     case Type::ObjCObjectPointer:
3198       Result.Namespaces.insert(Result.S.Context.getTranslationUnitDecl());
3199       break;
3200 
3201     // Atomic types are just wrappers; use the associations of the
3202     // contained type.
3203     case Type::Atomic:
3204       T = cast<AtomicType>(T)->getValueType().getTypePtr();
3205       continue;
3206     case Type::Pipe:
3207       T = cast<PipeType>(T)->getElementType().getTypePtr();
3208       continue;
3209 
3210     // Array parameter types are treated as fundamental types.
3211     case Type::ArrayParameter:
3212       break;
3213     }
3214 
3215     if (Queue.empty())
3216       break;
3217     T = Queue.pop_back_val();
3218   }
3219 }
3220 
3221 void Sema::FindAssociatedClassesAndNamespaces(
3222     SourceLocation InstantiationLoc, ArrayRef<Expr *> Args,
3223     AssociatedNamespaceSet &AssociatedNamespaces,
3224     AssociatedClassSet &AssociatedClasses) {
3225   AssociatedNamespaces.clear();
3226   AssociatedClasses.clear();
3227 
3228   AssociatedLookup Result(*this, InstantiationLoc,
3229                           AssociatedNamespaces, AssociatedClasses);
3230 
3231   // C++ [basic.lookup.koenig]p2:
3232   //   For each argument type T in the function call, there is a set
3233   //   of zero or more associated namespaces and a set of zero or more
3234   //   associated classes to be considered. The sets of namespaces and
3235   //   classes is determined entirely by the types of the function
3236   //   arguments (and the namespace of any template template
3237   //   argument).
3238   for (unsigned ArgIdx = 0; ArgIdx != Args.size(); ++ArgIdx) {
3239     Expr *Arg = Args[ArgIdx];
3240 
3241     if (Arg->getType() != Context.OverloadTy) {
3242       addAssociatedClassesAndNamespaces(Result, Arg->getType());
3243       continue;
3244     }
3245 
3246     // [...] In addition, if the argument is the name or address of a
3247     // set of overloaded functions and/or function templates, its
3248     // associated classes and namespaces are the union of those
3249     // associated with each of the members of the set: the namespace
3250     // in which the function or function template is defined and the
3251     // classes and namespaces associated with its (non-dependent)
3252     // parameter types and return type.
3253     OverloadExpr *OE = OverloadExpr::find(Arg).Expression;
3254 
3255     for (const NamedDecl *D : OE->decls()) {
3256       // Look through any using declarations to find the underlying function.
3257       const FunctionDecl *FDecl = D->getUnderlyingDecl()->getAsFunction();
3258 
3259       // Add the classes and namespaces associated with the parameter
3260       // types and return type of this function.
3261       addAssociatedClassesAndNamespaces(Result, FDecl->getType());
3262     }
3263   }
3264 }
3265 
3266 NamedDecl *Sema::LookupSingleName(Scope *S, DeclarationName Name,
3267                                   SourceLocation Loc,
3268                                   LookupNameKind NameKind,
3269                                   RedeclarationKind Redecl) {
3270   LookupResult R(*this, Name, Loc, NameKind, Redecl);
3271   LookupName(R, S);
3272   return R.getAsSingle<NamedDecl>();
3273 }
3274 
3275 void Sema::LookupOverloadedOperatorName(OverloadedOperatorKind Op, Scope *S,
3276                                         UnresolvedSetImpl &Functions) {
3277   // C++ [over.match.oper]p3:
3278   //     -- The set of non-member candidates is the result of the
3279   //        unqualified lookup of operator@ in the context of the
3280   //        expression according to the usual rules for name lookup in
3281   //        unqualified function calls (3.4.2) except that all member
3282   //        functions are ignored.
3283   DeclarationName OpName = Context.DeclarationNames.getCXXOperatorName(Op);
3284   LookupResult Operators(*this, OpName, SourceLocation(), LookupOperatorName);
3285   LookupName(Operators, S);
3286 
3287   assert(!Operators.isAmbiguous() && "Operator lookup cannot be ambiguous");
3288   Functions.append(Operators.begin(), Operators.end());
3289 }
3290 
3291 Sema::SpecialMemberOverloadResult
3292 Sema::LookupSpecialMember(CXXRecordDecl *RD, CXXSpecialMemberKind SM,
3293                           bool ConstArg, bool VolatileArg, bool RValueThis,
3294                           bool ConstThis, bool VolatileThis) {
3295   assert(CanDeclareSpecialMemberFunction(RD) &&
3296          "doing special member lookup into record that isn't fully complete");
3297   RD = RD->getDefinition();
3298   if (RValueThis || ConstThis || VolatileThis)
3299     assert((SM == CXXSpecialMemberKind::CopyAssignment ||
3300             SM == CXXSpecialMemberKind::MoveAssignment) &&
3301            "constructors and destructors always have unqualified lvalue this");
3302   if (ConstArg || VolatileArg)
3303     assert((SM != CXXSpecialMemberKind::DefaultConstructor &&
3304             SM != CXXSpecialMemberKind::Destructor) &&
3305            "parameter-less special members can't have qualified arguments");
3306 
3307   // FIXME: Get the caller to pass in a location for the lookup.
3308   SourceLocation LookupLoc = RD->getLocation();
3309 
3310   llvm::FoldingSetNodeID ID;
3311   ID.AddPointer(RD);
3312   ID.AddInteger(llvm::to_underlying(SM));
3313   ID.AddInteger(ConstArg);
3314   ID.AddInteger(VolatileArg);
3315   ID.AddInteger(RValueThis);
3316   ID.AddInteger(ConstThis);
3317   ID.AddInteger(VolatileThis);
3318 
3319   void *InsertPoint;
3320   SpecialMemberOverloadResultEntry *Result =
3321     SpecialMemberCache.FindNodeOrInsertPos(ID, InsertPoint);
3322 
3323   // This was already cached
3324   if (Result)
3325     return *Result;
3326 
3327   Result = BumpAlloc.Allocate<SpecialMemberOverloadResultEntry>();
3328   Result = new (Result) SpecialMemberOverloadResultEntry(ID);
3329   SpecialMemberCache.InsertNode(Result, InsertPoint);
3330 
3331   if (SM == CXXSpecialMemberKind::Destructor) {
3332     if (RD->needsImplicitDestructor()) {
3333       runWithSufficientStackSpace(RD->getLocation(), [&] {
3334         DeclareImplicitDestructor(RD);
3335       });
3336     }
3337     CXXDestructorDecl *DD = RD->getDestructor();
3338     Result->setMethod(DD);
3339     Result->setKind(DD && !DD->isDeleted()
3340                         ? SpecialMemberOverloadResult::Success
3341                         : SpecialMemberOverloadResult::NoMemberOrDeleted);
3342     return *Result;
3343   }
3344 
3345   // Prepare for overload resolution. Here we construct a synthetic argument
3346   // if necessary and make sure that implicit functions are declared.
3347   CanQualType CanTy = Context.getCanonicalType(Context.getTagDeclType(RD));
3348   DeclarationName Name;
3349   Expr *Arg = nullptr;
3350   unsigned NumArgs;
3351 
3352   QualType ArgType = CanTy;
3353   ExprValueKind VK = VK_LValue;
3354 
3355   if (SM == CXXSpecialMemberKind::DefaultConstructor) {
3356     Name = Context.DeclarationNames.getCXXConstructorName(CanTy);
3357     NumArgs = 0;
3358     if (RD->needsImplicitDefaultConstructor()) {
3359       runWithSufficientStackSpace(RD->getLocation(), [&] {
3360         DeclareImplicitDefaultConstructor(RD);
3361       });
3362     }
3363   } else {
3364     if (SM == CXXSpecialMemberKind::CopyConstructor ||
3365         SM == CXXSpecialMemberKind::MoveConstructor) {
3366       Name = Context.DeclarationNames.getCXXConstructorName(CanTy);
3367       if (RD->needsImplicitCopyConstructor()) {
3368         runWithSufficientStackSpace(RD->getLocation(), [&] {
3369           DeclareImplicitCopyConstructor(RD);
3370         });
3371       }
3372       if (getLangOpts().CPlusPlus11 && RD->needsImplicitMoveConstructor()) {
3373         runWithSufficientStackSpace(RD->getLocation(), [&] {
3374           DeclareImplicitMoveConstructor(RD);
3375         });
3376       }
3377     } else {
3378       Name = Context.DeclarationNames.getCXXOperatorName(OO_Equal);
3379       if (RD->needsImplicitCopyAssignment()) {
3380         runWithSufficientStackSpace(RD->getLocation(), [&] {
3381           DeclareImplicitCopyAssignment(RD);
3382         });
3383       }
3384       if (getLangOpts().CPlusPlus11 && RD->needsImplicitMoveAssignment()) {
3385         runWithSufficientStackSpace(RD->getLocation(), [&] {
3386           DeclareImplicitMoveAssignment(RD);
3387         });
3388       }
3389     }
3390 
3391     if (ConstArg)
3392       ArgType.addConst();
3393     if (VolatileArg)
3394       ArgType.addVolatile();
3395 
3396     // This isn't /really/ specified by the standard, but it's implied
3397     // we should be working from a PRValue in the case of move to ensure
3398     // that we prefer to bind to rvalue references, and an LValue in the
3399     // case of copy to ensure we don't bind to rvalue references.
3400     // Possibly an XValue is actually correct in the case of move, but
3401     // there is no semantic difference for class types in this restricted
3402     // case.
3403     if (SM == CXXSpecialMemberKind::CopyConstructor ||
3404         SM == CXXSpecialMemberKind::CopyAssignment)
3405       VK = VK_LValue;
3406     else
3407       VK = VK_PRValue;
3408   }
3409 
3410   OpaqueValueExpr FakeArg(LookupLoc, ArgType, VK);
3411 
3412   if (SM != CXXSpecialMemberKind::DefaultConstructor) {
3413     NumArgs = 1;
3414     Arg = &FakeArg;
3415   }
3416 
3417   // Create the object argument
3418   QualType ThisTy = CanTy;
3419   if (ConstThis)
3420     ThisTy.addConst();
3421   if (VolatileThis)
3422     ThisTy.addVolatile();
3423   Expr::Classification Classification =
3424       OpaqueValueExpr(LookupLoc, ThisTy, RValueThis ? VK_PRValue : VK_LValue)
3425           .Classify(Context);
3426 
3427   // Now we perform lookup on the name we computed earlier and do overload
3428   // resolution. Lookup is only performed directly into the class since there
3429   // will always be a (possibly implicit) declaration to shadow any others.
3430   OverloadCandidateSet OCS(LookupLoc, OverloadCandidateSet::CSK_Normal);
3431   DeclContext::lookup_result R = RD->lookup(Name);
3432 
3433   if (R.empty()) {
3434     // We might have no default constructor because we have a lambda's closure
3435     // type, rather than because there's some other declared constructor.
3436     // Every class has a copy/move constructor, copy/move assignment, and
3437     // destructor.
3438     assert(SM == CXXSpecialMemberKind::DefaultConstructor &&
3439            "lookup for a constructor or assignment operator was empty");
3440     Result->setMethod(nullptr);
3441     Result->setKind(SpecialMemberOverloadResult::NoMemberOrDeleted);
3442     return *Result;
3443   }
3444 
3445   // Copy the candidates as our processing of them may load new declarations
3446   // from an external source and invalidate lookup_result.
3447   SmallVector<NamedDecl *, 8> Candidates(R.begin(), R.end());
3448 
3449   for (NamedDecl *CandDecl : Candidates) {
3450     if (CandDecl->isInvalidDecl())
3451       continue;
3452 
3453     DeclAccessPair Cand = DeclAccessPair::make(CandDecl, AS_public);
3454     auto CtorInfo = getConstructorInfo(Cand);
3455     if (CXXMethodDecl *M = dyn_cast<CXXMethodDecl>(Cand->getUnderlyingDecl())) {
3456       if (SM == CXXSpecialMemberKind::CopyAssignment ||
3457           SM == CXXSpecialMemberKind::MoveAssignment)
3458         AddMethodCandidate(M, Cand, RD, ThisTy, Classification,
3459                            llvm::ArrayRef(&Arg, NumArgs), OCS, true);
3460       else if (CtorInfo)
3461         AddOverloadCandidate(CtorInfo.Constructor, CtorInfo.FoundDecl,
3462                              llvm::ArrayRef(&Arg, NumArgs), OCS,
3463                              /*SuppressUserConversions*/ true);
3464       else
3465         AddOverloadCandidate(M, Cand, llvm::ArrayRef(&Arg, NumArgs), OCS,
3466                              /*SuppressUserConversions*/ true);
3467     } else if (FunctionTemplateDecl *Tmpl =
3468                  dyn_cast<FunctionTemplateDecl>(Cand->getUnderlyingDecl())) {
3469       if (SM == CXXSpecialMemberKind::CopyAssignment ||
3470           SM == CXXSpecialMemberKind::MoveAssignment)
3471         AddMethodTemplateCandidate(Tmpl, Cand, RD, nullptr, ThisTy,
3472                                    Classification,
3473                                    llvm::ArrayRef(&Arg, NumArgs), OCS, true);
3474       else if (CtorInfo)
3475         AddTemplateOverloadCandidate(CtorInfo.ConstructorTmpl,
3476                                      CtorInfo.FoundDecl, nullptr,
3477                                      llvm::ArrayRef(&Arg, NumArgs), OCS, true);
3478       else
3479         AddTemplateOverloadCandidate(Tmpl, Cand, nullptr,
3480                                      llvm::ArrayRef(&Arg, NumArgs), OCS, true);
3481     } else {
3482       assert(isa<UsingDecl>(Cand.getDecl()) &&
3483              "illegal Kind of operator = Decl");
3484     }
3485   }
3486 
3487   OverloadCandidateSet::iterator Best;
3488   switch (OCS.BestViableFunction(*this, LookupLoc, Best)) {
3489     case OR_Success:
3490       Result->setMethod(cast<CXXMethodDecl>(Best->Function));
3491       Result->setKind(SpecialMemberOverloadResult::Success);
3492       break;
3493 
3494     case OR_Deleted:
3495       Result->setMethod(cast<CXXMethodDecl>(Best->Function));
3496       Result->setKind(SpecialMemberOverloadResult::NoMemberOrDeleted);
3497       break;
3498 
3499     case OR_Ambiguous:
3500       Result->setMethod(nullptr);
3501       Result->setKind(SpecialMemberOverloadResult::Ambiguous);
3502       break;
3503 
3504     case OR_No_Viable_Function:
3505       Result->setMethod(nullptr);
3506       Result->setKind(SpecialMemberOverloadResult::NoMemberOrDeleted);
3507       break;
3508   }
3509 
3510   return *Result;
3511 }
3512 
3513 CXXConstructorDecl *Sema::LookupDefaultConstructor(CXXRecordDecl *Class) {
3514   SpecialMemberOverloadResult Result =
3515       LookupSpecialMember(Class, CXXSpecialMemberKind::DefaultConstructor,
3516                           false, false, false, false, false);
3517 
3518   return cast_or_null<CXXConstructorDecl>(Result.getMethod());
3519 }
3520 
3521 CXXConstructorDecl *Sema::LookupCopyingConstructor(CXXRecordDecl *Class,
3522                                                    unsigned Quals) {
3523   assert(!(Quals & ~(Qualifiers::Const | Qualifiers::Volatile)) &&
3524          "non-const, non-volatile qualifiers for copy ctor arg");
3525   SpecialMemberOverloadResult Result = LookupSpecialMember(
3526       Class, CXXSpecialMemberKind::CopyConstructor, Quals & Qualifiers::Const,
3527       Quals & Qualifiers::Volatile, false, false, false);
3528 
3529   return cast_or_null<CXXConstructorDecl>(Result.getMethod());
3530 }
3531 
3532 CXXConstructorDecl *Sema::LookupMovingConstructor(CXXRecordDecl *Class,
3533                                                   unsigned Quals) {
3534   SpecialMemberOverloadResult Result = LookupSpecialMember(
3535       Class, CXXSpecialMemberKind::MoveConstructor, Quals & Qualifiers::Const,
3536       Quals & Qualifiers::Volatile, false, false, false);
3537 
3538   return cast_or_null<CXXConstructorDecl>(Result.getMethod());
3539 }
3540 
3541 DeclContext::lookup_result Sema::LookupConstructors(CXXRecordDecl *Class) {
3542   // If the implicit constructors have not yet been declared, do so now.
3543   if (CanDeclareSpecialMemberFunction(Class)) {
3544     runWithSufficientStackSpace(Class->getLocation(), [&] {
3545       if (Class->needsImplicitDefaultConstructor())
3546         DeclareImplicitDefaultConstructor(Class);
3547       if (Class->needsImplicitCopyConstructor())
3548         DeclareImplicitCopyConstructor(Class);
3549       if (getLangOpts().CPlusPlus11 && Class->needsImplicitMoveConstructor())
3550         DeclareImplicitMoveConstructor(Class);
3551     });
3552   }
3553 
3554   CanQualType T = Context.getCanonicalType(Context.getTypeDeclType(Class));
3555   DeclarationName Name = Context.DeclarationNames.getCXXConstructorName(T);
3556   return Class->lookup(Name);
3557 }
3558 
3559 CXXMethodDecl *Sema::LookupCopyingAssignment(CXXRecordDecl *Class,
3560                                              unsigned Quals, bool RValueThis,
3561                                              unsigned ThisQuals) {
3562   assert(!(Quals & ~(Qualifiers::Const | Qualifiers::Volatile)) &&
3563          "non-const, non-volatile qualifiers for copy assignment arg");
3564   assert(!(ThisQuals & ~(Qualifiers::Const | Qualifiers::Volatile)) &&
3565          "non-const, non-volatile qualifiers for copy assignment this");
3566   SpecialMemberOverloadResult Result = LookupSpecialMember(
3567       Class, CXXSpecialMemberKind::CopyAssignment, Quals & Qualifiers::Const,
3568       Quals & Qualifiers::Volatile, RValueThis, ThisQuals & Qualifiers::Const,
3569       ThisQuals & Qualifiers::Volatile);
3570 
3571   return Result.getMethod();
3572 }
3573 
3574 CXXMethodDecl *Sema::LookupMovingAssignment(CXXRecordDecl *Class,
3575                                             unsigned Quals,
3576                                             bool RValueThis,
3577                                             unsigned ThisQuals) {
3578   assert(!(ThisQuals & ~(Qualifiers::Const | Qualifiers::Volatile)) &&
3579          "non-const, non-volatile qualifiers for copy assignment this");
3580   SpecialMemberOverloadResult Result = LookupSpecialMember(
3581       Class, CXXSpecialMemberKind::MoveAssignment, Quals & Qualifiers::Const,
3582       Quals & Qualifiers::Volatile, RValueThis, ThisQuals & Qualifiers::Const,
3583       ThisQuals & Qualifiers::Volatile);
3584 
3585   return Result.getMethod();
3586 }
3587 
3588 CXXDestructorDecl *Sema::LookupDestructor(CXXRecordDecl *Class) {
3589   return cast_or_null<CXXDestructorDecl>(
3590       LookupSpecialMember(Class, CXXSpecialMemberKind::Destructor, false, false,
3591                           false, false, false)
3592           .getMethod());
3593 }
3594 
3595 Sema::LiteralOperatorLookupResult
3596 Sema::LookupLiteralOperator(Scope *S, LookupResult &R,
3597                             ArrayRef<QualType> ArgTys, bool AllowRaw,
3598                             bool AllowTemplate, bool AllowStringTemplatePack,
3599                             bool DiagnoseMissing, StringLiteral *StringLit) {
3600   LookupName(R, S);
3601   assert(R.getResultKind() != LookupResult::Ambiguous &&
3602          "literal operator lookup can't be ambiguous");
3603 
3604   // Filter the lookup results appropriately.
3605   LookupResult::Filter F = R.makeFilter();
3606 
3607   bool AllowCooked = true;
3608   bool FoundRaw = false;
3609   bool FoundTemplate = false;
3610   bool FoundStringTemplatePack = false;
3611   bool FoundCooked = false;
3612 
3613   while (F.hasNext()) {
3614     Decl *D = F.next();
3615     if (UsingShadowDecl *USD = dyn_cast<UsingShadowDecl>(D))
3616       D = USD->getTargetDecl();
3617 
3618     // If the declaration we found is invalid, skip it.
3619     if (D->isInvalidDecl()) {
3620       F.erase();
3621       continue;
3622     }
3623 
3624     bool IsRaw = false;
3625     bool IsTemplate = false;
3626     bool IsStringTemplatePack = false;
3627     bool IsCooked = false;
3628 
3629     if (FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
3630       if (FD->getNumParams() == 1 &&
3631           FD->getParamDecl(0)->getType()->getAs<PointerType>())
3632         IsRaw = true;
3633       else if (FD->getNumParams() == ArgTys.size()) {
3634         IsCooked = true;
3635         for (unsigned ArgIdx = 0; ArgIdx != ArgTys.size(); ++ArgIdx) {
3636           QualType ParamTy = FD->getParamDecl(ArgIdx)->getType();
3637           if (!Context.hasSameUnqualifiedType(ArgTys[ArgIdx], ParamTy)) {
3638             IsCooked = false;
3639             break;
3640           }
3641         }
3642       }
3643     }
3644     if (FunctionTemplateDecl *FD = dyn_cast<FunctionTemplateDecl>(D)) {
3645       TemplateParameterList *Params = FD->getTemplateParameters();
3646       if (Params->size() == 1) {
3647         IsTemplate = true;
3648         if (!Params->getParam(0)->isTemplateParameterPack() && !StringLit) {
3649           // Implied but not stated: user-defined integer and floating literals
3650           // only ever use numeric literal operator templates, not templates
3651           // taking a parameter of class type.
3652           F.erase();
3653           continue;
3654         }
3655 
3656         // A string literal template is only considered if the string literal
3657         // is a well-formed template argument for the template parameter.
3658         if (StringLit) {
3659           SFINAETrap Trap(*this);
3660           SmallVector<TemplateArgument, 1> SugaredChecked, CanonicalChecked;
3661           TemplateArgumentLoc Arg(TemplateArgument(StringLit), StringLit);
3662           if (CheckTemplateArgument(
3663                   Params->getParam(0), Arg, FD, R.getNameLoc(), R.getNameLoc(),
3664                   0, SugaredChecked, CanonicalChecked, CTAK_Specified) ||
3665               Trap.hasErrorOccurred())
3666             IsTemplate = false;
3667         }
3668       } else {
3669         IsStringTemplatePack = true;
3670       }
3671     }
3672 
3673     if (AllowTemplate && StringLit && IsTemplate) {
3674       FoundTemplate = true;
3675       AllowRaw = false;
3676       AllowCooked = false;
3677       AllowStringTemplatePack = false;
3678       if (FoundRaw || FoundCooked || FoundStringTemplatePack) {
3679         F.restart();
3680         FoundRaw = FoundCooked = FoundStringTemplatePack = false;
3681       }
3682     } else if (AllowCooked && IsCooked) {
3683       FoundCooked = true;
3684       AllowRaw = false;
3685       AllowTemplate = StringLit;
3686       AllowStringTemplatePack = false;
3687       if (FoundRaw || FoundTemplate || FoundStringTemplatePack) {
3688         // Go through again and remove the raw and template decls we've
3689         // already found.
3690         F.restart();
3691         FoundRaw = FoundTemplate = FoundStringTemplatePack = false;
3692       }
3693     } else if (AllowRaw && IsRaw) {
3694       FoundRaw = true;
3695     } else if (AllowTemplate && IsTemplate) {
3696       FoundTemplate = true;
3697     } else if (AllowStringTemplatePack && IsStringTemplatePack) {
3698       FoundStringTemplatePack = true;
3699     } else {
3700       F.erase();
3701     }
3702   }
3703 
3704   F.done();
3705 
3706   // Per C++20 [lex.ext]p5, we prefer the template form over the non-template
3707   // form for string literal operator templates.
3708   if (StringLit && FoundTemplate)
3709     return LOLR_Template;
3710 
3711   // C++11 [lex.ext]p3, p4: If S contains a literal operator with a matching
3712   // parameter type, that is used in preference to a raw literal operator
3713   // or literal operator template.
3714   if (FoundCooked)
3715     return LOLR_Cooked;
3716 
3717   // C++11 [lex.ext]p3, p4: S shall contain a raw literal operator or a literal
3718   // operator template, but not both.
3719   if (FoundRaw && FoundTemplate) {
3720     Diag(R.getNameLoc(), diag::err_ovl_ambiguous_call) << R.getLookupName();
3721     for (const NamedDecl *D : R)
3722       NoteOverloadCandidate(D, D->getUnderlyingDecl()->getAsFunction());
3723     return LOLR_Error;
3724   }
3725 
3726   if (FoundRaw)
3727     return LOLR_Raw;
3728 
3729   if (FoundTemplate)
3730     return LOLR_Template;
3731 
3732   if (FoundStringTemplatePack)
3733     return LOLR_StringTemplatePack;
3734 
3735   // Didn't find anything we could use.
3736   if (DiagnoseMissing) {
3737     Diag(R.getNameLoc(), diag::err_ovl_no_viable_literal_operator)
3738         << R.getLookupName() << (int)ArgTys.size() << ArgTys[0]
3739         << (ArgTys.size() == 2 ? ArgTys[1] : QualType()) << AllowRaw
3740         << (AllowTemplate || AllowStringTemplatePack);
3741     return LOLR_Error;
3742   }
3743 
3744   return LOLR_ErrorNoDiagnostic;
3745 }
3746 
3747 void ADLResult::insert(NamedDecl *New) {
3748   NamedDecl *&Old = Decls[cast<NamedDecl>(New->getCanonicalDecl())];
3749 
3750   // If we haven't yet seen a decl for this key, or the last decl
3751   // was exactly this one, we're done.
3752   if (Old == nullptr || Old == New) {
3753     Old = New;
3754     return;
3755   }
3756 
3757   // Otherwise, decide which is a more recent redeclaration.
3758   FunctionDecl *OldFD = Old->getAsFunction();
3759   FunctionDecl *NewFD = New->getAsFunction();
3760 
3761   FunctionDecl *Cursor = NewFD;
3762   while (true) {
3763     Cursor = Cursor->getPreviousDecl();
3764 
3765     // If we got to the end without finding OldFD, OldFD is the newer
3766     // declaration;  leave things as they are.
3767     if (!Cursor) return;
3768 
3769     // If we do find OldFD, then NewFD is newer.
3770     if (Cursor == OldFD) break;
3771 
3772     // Otherwise, keep looking.
3773   }
3774 
3775   Old = New;
3776 }
3777 
3778 void Sema::ArgumentDependentLookup(DeclarationName Name, SourceLocation Loc,
3779                                    ArrayRef<Expr *> Args, ADLResult &Result) {
3780   // Find all of the associated namespaces and classes based on the
3781   // arguments we have.
3782   AssociatedNamespaceSet AssociatedNamespaces;
3783   AssociatedClassSet AssociatedClasses;
3784   FindAssociatedClassesAndNamespaces(Loc, Args,
3785                                      AssociatedNamespaces,
3786                                      AssociatedClasses);
3787 
3788   // C++ [basic.lookup.argdep]p3:
3789   //   Let X be the lookup set produced by unqualified lookup (3.4.1)
3790   //   and let Y be the lookup set produced by argument dependent
3791   //   lookup (defined as follows). If X contains [...] then Y is
3792   //   empty. Otherwise Y is the set of declarations found in the
3793   //   namespaces associated with the argument types as described
3794   //   below. The set of declarations found by the lookup of the name
3795   //   is the union of X and Y.
3796   //
3797   // Here, we compute Y and add its members to the overloaded
3798   // candidate set.
3799   for (auto *NS : AssociatedNamespaces) {
3800     //   When considering an associated namespace, the lookup is the
3801     //   same as the lookup performed when the associated namespace is
3802     //   used as a qualifier (3.4.3.2) except that:
3803     //
3804     //     -- Any using-directives in the associated namespace are
3805     //        ignored.
3806     //
3807     //     -- Any namespace-scope friend functions declared in
3808     //        associated classes are visible within their respective
3809     //        namespaces even if they are not visible during an ordinary
3810     //        lookup (11.4).
3811     //
3812     // C++20 [basic.lookup.argdep] p4.3
3813     //     -- are exported, are attached to a named module M, do not appear
3814     //        in the translation unit containing the point of the lookup, and
3815     //        have the same innermost enclosing non-inline namespace scope as
3816     //        a declaration of an associated entity attached to M.
3817     DeclContext::lookup_result R = NS->lookup(Name);
3818     for (auto *D : R) {
3819       auto *Underlying = D;
3820       if (auto *USD = dyn_cast<UsingShadowDecl>(D))
3821         Underlying = USD->getTargetDecl();
3822 
3823       if (!isa<FunctionDecl>(Underlying) &&
3824           !isa<FunctionTemplateDecl>(Underlying))
3825         continue;
3826 
3827       // The declaration is visible to argument-dependent lookup if either
3828       // it's ordinarily visible or declared as a friend in an associated
3829       // class.
3830       bool Visible = false;
3831       for (D = D->getMostRecentDecl(); D;
3832            D = cast_or_null<NamedDecl>(D->getPreviousDecl())) {
3833         if (D->getIdentifierNamespace() & Decl::IDNS_Ordinary) {
3834           if (isVisible(D)) {
3835             Visible = true;
3836             break;
3837           }
3838 
3839           if (!getLangOpts().CPlusPlusModules)
3840             continue;
3841 
3842           if (D->isInExportDeclContext()) {
3843             Module *FM = D->getOwningModule();
3844             // C++20 [basic.lookup.argdep] p4.3 .. are exported ...
3845             // exports are only valid in module purview and outside of any
3846             // PMF (although a PMF should not even be present in a module
3847             // with an import).
3848             assert(FM && FM->isNamedModule() && !FM->isPrivateModule() &&
3849                    "bad export context");
3850             // .. are attached to a named module M, do not appear in the
3851             // translation unit containing the point of the lookup..
3852             if (D->isInAnotherModuleUnit() &&
3853                 llvm::any_of(AssociatedClasses, [&](auto *E) {
3854                   // ... and have the same innermost enclosing non-inline
3855                   // namespace scope as a declaration of an associated entity
3856                   // attached to M
3857                   if (E->getOwningModule() != FM)
3858                     return false;
3859                   // TODO: maybe this could be cached when generating the
3860                   // associated namespaces / entities.
3861                   DeclContext *Ctx = E->getDeclContext();
3862                   while (!Ctx->isFileContext() || Ctx->isInlineNamespace())
3863                     Ctx = Ctx->getParent();
3864                   return Ctx == NS;
3865                 })) {
3866               Visible = true;
3867               break;
3868             }
3869           }
3870         } else if (D->getFriendObjectKind()) {
3871           auto *RD = cast<CXXRecordDecl>(D->getLexicalDeclContext());
3872           // [basic.lookup.argdep]p4:
3873           //   Argument-dependent lookup finds all declarations of functions and
3874           //   function templates that
3875           //  - ...
3876           //  - are declared as a friend ([class.friend]) of any class with a
3877           //  reachable definition in the set of associated entities,
3878           //
3879           // FIXME: If there's a merged definition of D that is reachable, then
3880           // the friend declaration should be considered.
3881           if (AssociatedClasses.count(RD) && isReachable(D)) {
3882             Visible = true;
3883             break;
3884           }
3885         }
3886       }
3887 
3888       // FIXME: Preserve D as the FoundDecl.
3889       if (Visible)
3890         Result.insert(Underlying);
3891     }
3892   }
3893 }
3894 
3895 //----------------------------------------------------------------------------
3896 // Search for all visible declarations.
3897 //----------------------------------------------------------------------------
3898 VisibleDeclConsumer::~VisibleDeclConsumer() { }
3899 
3900 bool VisibleDeclConsumer::includeHiddenDecls() const { return false; }
3901 
3902 namespace {
3903 
3904 class ShadowContextRAII;
3905 
3906 class VisibleDeclsRecord {
3907 public:
3908   /// An entry in the shadow map, which is optimized to store a
3909   /// single declaration (the common case) but can also store a list
3910   /// of declarations.
3911   typedef llvm::TinyPtrVector<NamedDecl*> ShadowMapEntry;
3912 
3913 private:
3914   /// A mapping from declaration names to the declarations that have
3915   /// this name within a particular scope.
3916   typedef llvm::DenseMap<DeclarationName, ShadowMapEntry> ShadowMap;
3917 
3918   /// A list of shadow maps, which is used to model name hiding.
3919   std::list<ShadowMap> ShadowMaps;
3920 
3921   /// The declaration contexts we have already visited.
3922   llvm::SmallPtrSet<DeclContext *, 8> VisitedContexts;
3923 
3924   friend class ShadowContextRAII;
3925 
3926 public:
3927   /// Determine whether we have already visited this context
3928   /// (and, if not, note that we are going to visit that context now).
3929   bool visitedContext(DeclContext *Ctx) {
3930     return !VisitedContexts.insert(Ctx).second;
3931   }
3932 
3933   bool alreadyVisitedContext(DeclContext *Ctx) {
3934     return VisitedContexts.count(Ctx);
3935   }
3936 
3937   /// Determine whether the given declaration is hidden in the
3938   /// current scope.
3939   ///
3940   /// \returns the declaration that hides the given declaration, or
3941   /// NULL if no such declaration exists.
3942   NamedDecl *checkHidden(NamedDecl *ND);
3943 
3944   /// Add a declaration to the current shadow map.
3945   void add(NamedDecl *ND) {
3946     ShadowMaps.back()[ND->getDeclName()].push_back(ND);
3947   }
3948 };
3949 
3950 /// RAII object that records when we've entered a shadow context.
3951 class ShadowContextRAII {
3952   VisibleDeclsRecord &Visible;
3953 
3954   typedef VisibleDeclsRecord::ShadowMap ShadowMap;
3955 
3956 public:
3957   ShadowContextRAII(VisibleDeclsRecord &Visible) : Visible(Visible) {
3958     Visible.ShadowMaps.emplace_back();
3959   }
3960 
3961   ~ShadowContextRAII() {
3962     Visible.ShadowMaps.pop_back();
3963   }
3964 };
3965 
3966 } // end anonymous namespace
3967 
3968 NamedDecl *VisibleDeclsRecord::checkHidden(NamedDecl *ND) {
3969   unsigned IDNS = ND->getIdentifierNamespace();
3970   std::list<ShadowMap>::reverse_iterator SM = ShadowMaps.rbegin();
3971   for (std::list<ShadowMap>::reverse_iterator SMEnd = ShadowMaps.rend();
3972        SM != SMEnd; ++SM) {
3973     ShadowMap::iterator Pos = SM->find(ND->getDeclName());
3974     if (Pos == SM->end())
3975       continue;
3976 
3977     for (auto *D : Pos->second) {
3978       // A tag declaration does not hide a non-tag declaration.
3979       if (D->hasTagIdentifierNamespace() &&
3980           (IDNS & (Decl::IDNS_Member | Decl::IDNS_Ordinary |
3981                    Decl::IDNS_ObjCProtocol)))
3982         continue;
3983 
3984       // Protocols are in distinct namespaces from everything else.
3985       if (((D->getIdentifierNamespace() & Decl::IDNS_ObjCProtocol)
3986            || (IDNS & Decl::IDNS_ObjCProtocol)) &&
3987           D->getIdentifierNamespace() != IDNS)
3988         continue;
3989 
3990       // Functions and function templates in the same scope overload
3991       // rather than hide.  FIXME: Look for hiding based on function
3992       // signatures!
3993       if (D->getUnderlyingDecl()->isFunctionOrFunctionTemplate() &&
3994           ND->getUnderlyingDecl()->isFunctionOrFunctionTemplate() &&
3995           SM == ShadowMaps.rbegin())
3996         continue;
3997 
3998       // A shadow declaration that's created by a resolved using declaration
3999       // is not hidden by the same using declaration.
4000       if (isa<UsingShadowDecl>(ND) && isa<UsingDecl>(D) &&
4001           cast<UsingShadowDecl>(ND)->getIntroducer() == D)
4002         continue;
4003 
4004       // We've found a declaration that hides this one.
4005       return D;
4006     }
4007   }
4008 
4009   return nullptr;
4010 }
4011 
4012 namespace {
4013 class LookupVisibleHelper {
4014 public:
4015   LookupVisibleHelper(VisibleDeclConsumer &Consumer, bool IncludeDependentBases,
4016                       bool LoadExternal)
4017       : Consumer(Consumer), IncludeDependentBases(IncludeDependentBases),
4018         LoadExternal(LoadExternal) {}
4019 
4020   void lookupVisibleDecls(Sema &SemaRef, Scope *S, Sema::LookupNameKind Kind,
4021                           bool IncludeGlobalScope) {
4022     // Determine the set of using directives available during
4023     // unqualified name lookup.
4024     Scope *Initial = S;
4025     UnqualUsingDirectiveSet UDirs(SemaRef);
4026     if (SemaRef.getLangOpts().CPlusPlus) {
4027       // Find the first namespace or translation-unit scope.
4028       while (S && !isNamespaceOrTranslationUnitScope(S))
4029         S = S->getParent();
4030 
4031       UDirs.visitScopeChain(Initial, S);
4032     }
4033     UDirs.done();
4034 
4035     // Look for visible declarations.
4036     LookupResult Result(SemaRef, DeclarationName(), SourceLocation(), Kind);
4037     Result.setAllowHidden(Consumer.includeHiddenDecls());
4038     if (!IncludeGlobalScope)
4039       Visited.visitedContext(SemaRef.getASTContext().getTranslationUnitDecl());
4040     ShadowContextRAII Shadow(Visited);
4041     lookupInScope(Initial, Result, UDirs);
4042   }
4043 
4044   void lookupVisibleDecls(Sema &SemaRef, DeclContext *Ctx,
4045                           Sema::LookupNameKind Kind, bool IncludeGlobalScope) {
4046     LookupResult Result(SemaRef, DeclarationName(), SourceLocation(), Kind);
4047     Result.setAllowHidden(Consumer.includeHiddenDecls());
4048     if (!IncludeGlobalScope)
4049       Visited.visitedContext(SemaRef.getASTContext().getTranslationUnitDecl());
4050 
4051     ShadowContextRAII Shadow(Visited);
4052     lookupInDeclContext(Ctx, Result, /*QualifiedNameLookup=*/true,
4053                         /*InBaseClass=*/false);
4054   }
4055 
4056 private:
4057   void lookupInDeclContext(DeclContext *Ctx, LookupResult &Result,
4058                            bool QualifiedNameLookup, bool InBaseClass) {
4059     if (!Ctx)
4060       return;
4061 
4062     // Make sure we don't visit the same context twice.
4063     if (Visited.visitedContext(Ctx->getPrimaryContext()))
4064       return;
4065 
4066     Consumer.EnteredContext(Ctx);
4067 
4068     // Outside C++, lookup results for the TU live on identifiers.
4069     if (isa<TranslationUnitDecl>(Ctx) &&
4070         !Result.getSema().getLangOpts().CPlusPlus) {
4071       auto &S = Result.getSema();
4072       auto &Idents = S.Context.Idents;
4073 
4074       // Ensure all external identifiers are in the identifier table.
4075       if (LoadExternal)
4076         if (IdentifierInfoLookup *External =
4077                 Idents.getExternalIdentifierLookup()) {
4078           std::unique_ptr<IdentifierIterator> Iter(External->getIdentifiers());
4079           for (StringRef Name = Iter->Next(); !Name.empty();
4080                Name = Iter->Next())
4081             Idents.get(Name);
4082         }
4083 
4084       // Walk all lookup results in the TU for each identifier.
4085       for (const auto &Ident : Idents) {
4086         for (auto I = S.IdResolver.begin(Ident.getValue()),
4087                   E = S.IdResolver.end();
4088              I != E; ++I) {
4089           if (S.IdResolver.isDeclInScope(*I, Ctx)) {
4090             if (NamedDecl *ND = Result.getAcceptableDecl(*I)) {
4091               Consumer.FoundDecl(ND, Visited.checkHidden(ND), Ctx, InBaseClass);
4092               Visited.add(ND);
4093             }
4094           }
4095         }
4096       }
4097 
4098       return;
4099     }
4100 
4101     if (CXXRecordDecl *Class = dyn_cast<CXXRecordDecl>(Ctx))
4102       Result.getSema().ForceDeclarationOfImplicitMembers(Class);
4103 
4104     llvm::SmallVector<NamedDecl *, 4> DeclsToVisit;
4105     // We sometimes skip loading namespace-level results (they tend to be huge).
4106     bool Load = LoadExternal ||
4107                 !(isa<TranslationUnitDecl>(Ctx) || isa<NamespaceDecl>(Ctx));
4108     // Enumerate all of the results in this context.
4109     for (DeclContextLookupResult R :
4110          Load ? Ctx->lookups()
4111               : Ctx->noload_lookups(/*PreserveInternalState=*/false))
4112       for (auto *D : R)
4113         // Rather than visit immediately, we put ND into a vector and visit
4114         // all decls, in order, outside of this loop. The reason is that
4115         // Consumer.FoundDecl() and LookupResult::getAcceptableDecl(D)
4116         // may invalidate the iterators used in the two
4117         // loops above.
4118         DeclsToVisit.push_back(D);
4119 
4120     for (auto *D : DeclsToVisit)
4121       if (auto *ND = Result.getAcceptableDecl(D)) {
4122         Consumer.FoundDecl(ND, Visited.checkHidden(ND), Ctx, InBaseClass);
4123         Visited.add(ND);
4124       }
4125 
4126     DeclsToVisit.clear();
4127 
4128     // Traverse using directives for qualified name lookup.
4129     if (QualifiedNameLookup) {
4130       ShadowContextRAII Shadow(Visited);
4131       for (auto *I : Ctx->using_directives()) {
4132         if (!Result.getSema().isVisible(I))
4133           continue;
4134         lookupInDeclContext(I->getNominatedNamespace(), Result,
4135                             QualifiedNameLookup, InBaseClass);
4136       }
4137     }
4138 
4139     // Traverse the contexts of inherited C++ classes.
4140     if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(Ctx)) {
4141       if (!Record->hasDefinition())
4142         return;
4143 
4144       for (const auto &B : Record->bases()) {
4145         QualType BaseType = B.getType();
4146 
4147         RecordDecl *RD;
4148         if (BaseType->isDependentType()) {
4149           if (!IncludeDependentBases) {
4150             // Don't look into dependent bases, because name lookup can't look
4151             // there anyway.
4152             continue;
4153           }
4154           const auto *TST = BaseType->getAs<TemplateSpecializationType>();
4155           if (!TST)
4156             continue;
4157           TemplateName TN = TST->getTemplateName();
4158           const auto *TD =
4159               dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl());
4160           if (!TD)
4161             continue;
4162           RD = TD->getTemplatedDecl();
4163         } else {
4164           const auto *Record = BaseType->getAs<RecordType>();
4165           if (!Record)
4166             continue;
4167           RD = Record->getDecl();
4168         }
4169 
4170         // FIXME: It would be nice to be able to determine whether referencing
4171         // a particular member would be ambiguous. For example, given
4172         //
4173         //   struct A { int member; };
4174         //   struct B { int member; };
4175         //   struct C : A, B { };
4176         //
4177         //   void f(C *c) { c->### }
4178         //
4179         // accessing 'member' would result in an ambiguity. However, we
4180         // could be smart enough to qualify the member with the base
4181         // class, e.g.,
4182         //
4183         //   c->B::member
4184         //
4185         // or
4186         //
4187         //   c->A::member
4188 
4189         // Find results in this base class (and its bases).
4190         ShadowContextRAII Shadow(Visited);
4191         lookupInDeclContext(RD, Result, QualifiedNameLookup,
4192                             /*InBaseClass=*/true);
4193       }
4194     }
4195 
4196     // Traverse the contexts of Objective-C classes.
4197     if (ObjCInterfaceDecl *IFace = dyn_cast<ObjCInterfaceDecl>(Ctx)) {
4198       // Traverse categories.
4199       for (auto *Cat : IFace->visible_categories()) {
4200         ShadowContextRAII Shadow(Visited);
4201         lookupInDeclContext(Cat, Result, QualifiedNameLookup,
4202                             /*InBaseClass=*/false);
4203       }
4204 
4205       // Traverse protocols.
4206       for (auto *I : IFace->all_referenced_protocols()) {
4207         ShadowContextRAII Shadow(Visited);
4208         lookupInDeclContext(I, Result, QualifiedNameLookup,
4209                             /*InBaseClass=*/false);
4210       }
4211 
4212       // Traverse the superclass.
4213       if (IFace->getSuperClass()) {
4214         ShadowContextRAII Shadow(Visited);
4215         lookupInDeclContext(IFace->getSuperClass(), Result, QualifiedNameLookup,
4216                             /*InBaseClass=*/true);
4217       }
4218 
4219       // If there is an implementation, traverse it. We do this to find
4220       // synthesized ivars.
4221       if (IFace->getImplementation()) {
4222         ShadowContextRAII Shadow(Visited);
4223         lookupInDeclContext(IFace->getImplementation(), Result,
4224                             QualifiedNameLookup, InBaseClass);
4225       }
4226     } else if (ObjCProtocolDecl *Protocol = dyn_cast<ObjCProtocolDecl>(Ctx)) {
4227       for (auto *I : Protocol->protocols()) {
4228         ShadowContextRAII Shadow(Visited);
4229         lookupInDeclContext(I, Result, QualifiedNameLookup,
4230                             /*InBaseClass=*/false);
4231       }
4232     } else if (ObjCCategoryDecl *Category = dyn_cast<ObjCCategoryDecl>(Ctx)) {
4233       for (auto *I : Category->protocols()) {
4234         ShadowContextRAII Shadow(Visited);
4235         lookupInDeclContext(I, Result, QualifiedNameLookup,
4236                             /*InBaseClass=*/false);
4237       }
4238 
4239       // If there is an implementation, traverse it.
4240       if (Category->getImplementation()) {
4241         ShadowContextRAII Shadow(Visited);
4242         lookupInDeclContext(Category->getImplementation(), Result,
4243                             QualifiedNameLookup, /*InBaseClass=*/true);
4244       }
4245     }
4246   }
4247 
4248   void lookupInScope(Scope *S, LookupResult &Result,
4249                      UnqualUsingDirectiveSet &UDirs) {
4250     // No clients run in this mode and it's not supported. Please add tests and
4251     // remove the assertion if you start relying on it.
4252     assert(!IncludeDependentBases && "Unsupported flag for lookupInScope");
4253 
4254     if (!S)
4255       return;
4256 
4257     if (!S->getEntity() ||
4258         (!S->getParent() && !Visited.alreadyVisitedContext(S->getEntity())) ||
4259         (S->getEntity())->isFunctionOrMethod()) {
4260       FindLocalExternScope FindLocals(Result);
4261       // Walk through the declarations in this Scope. The consumer might add new
4262       // decls to the scope as part of deserialization, so make a copy first.
4263       SmallVector<Decl *, 8> ScopeDecls(S->decls().begin(), S->decls().end());
4264       for (Decl *D : ScopeDecls) {
4265         if (NamedDecl *ND = dyn_cast<NamedDecl>(D))
4266           if ((ND = Result.getAcceptableDecl(ND))) {
4267             Consumer.FoundDecl(ND, Visited.checkHidden(ND), nullptr, false);
4268             Visited.add(ND);
4269           }
4270       }
4271     }
4272 
4273     DeclContext *Entity = S->getLookupEntity();
4274     if (Entity) {
4275       // Look into this scope's declaration context, along with any of its
4276       // parent lookup contexts (e.g., enclosing classes), up to the point
4277       // where we hit the context stored in the next outer scope.
4278       DeclContext *OuterCtx = findOuterContext(S);
4279 
4280       for (DeclContext *Ctx = Entity; Ctx && !Ctx->Equals(OuterCtx);
4281            Ctx = Ctx->getLookupParent()) {
4282         if (ObjCMethodDecl *Method = dyn_cast<ObjCMethodDecl>(Ctx)) {
4283           if (Method->isInstanceMethod()) {
4284             // For instance methods, look for ivars in the method's interface.
4285             LookupResult IvarResult(Result.getSema(), Result.getLookupName(),
4286                                     Result.getNameLoc(),
4287                                     Sema::LookupMemberName);
4288             if (ObjCInterfaceDecl *IFace = Method->getClassInterface()) {
4289               lookupInDeclContext(IFace, IvarResult,
4290                                   /*QualifiedNameLookup=*/false,
4291                                   /*InBaseClass=*/false);
4292             }
4293           }
4294 
4295           // We've already performed all of the name lookup that we need
4296           // to for Objective-C methods; the next context will be the
4297           // outer scope.
4298           break;
4299         }
4300 
4301         if (Ctx->isFunctionOrMethod())
4302           continue;
4303 
4304         lookupInDeclContext(Ctx, Result, /*QualifiedNameLookup=*/false,
4305                             /*InBaseClass=*/false);
4306       }
4307     } else if (!S->getParent()) {
4308       // Look into the translation unit scope. We walk through the translation
4309       // unit's declaration context, because the Scope itself won't have all of
4310       // the declarations if we loaded a precompiled header.
4311       // FIXME: We would like the translation unit's Scope object to point to
4312       // the translation unit, so we don't need this special "if" branch.
4313       // However, doing so would force the normal C++ name-lookup code to look
4314       // into the translation unit decl when the IdentifierInfo chains would
4315       // suffice. Once we fix that problem (which is part of a more general
4316       // "don't look in DeclContexts unless we have to" optimization), we can
4317       // eliminate this.
4318       Entity = Result.getSema().Context.getTranslationUnitDecl();
4319       lookupInDeclContext(Entity, Result, /*QualifiedNameLookup=*/false,
4320                           /*InBaseClass=*/false);
4321     }
4322 
4323     if (Entity) {
4324       // Lookup visible declarations in any namespaces found by using
4325       // directives.
4326       for (const UnqualUsingEntry &UUE : UDirs.getNamespacesFor(Entity))
4327         lookupInDeclContext(
4328             const_cast<DeclContext *>(UUE.getNominatedNamespace()), Result,
4329             /*QualifiedNameLookup=*/false,
4330             /*InBaseClass=*/false);
4331     }
4332 
4333     // Lookup names in the parent scope.
4334     ShadowContextRAII Shadow(Visited);
4335     lookupInScope(S->getParent(), Result, UDirs);
4336   }
4337 
4338 private:
4339   VisibleDeclsRecord Visited;
4340   VisibleDeclConsumer &Consumer;
4341   bool IncludeDependentBases;
4342   bool LoadExternal;
4343 };
4344 } // namespace
4345 
4346 void Sema::LookupVisibleDecls(Scope *S, LookupNameKind Kind,
4347                               VisibleDeclConsumer &Consumer,
4348                               bool IncludeGlobalScope, bool LoadExternal) {
4349   LookupVisibleHelper H(Consumer, /*IncludeDependentBases=*/false,
4350                         LoadExternal);
4351   H.lookupVisibleDecls(*this, S, Kind, IncludeGlobalScope);
4352 }
4353 
4354 void Sema::LookupVisibleDecls(DeclContext *Ctx, LookupNameKind Kind,
4355                               VisibleDeclConsumer &Consumer,
4356                               bool IncludeGlobalScope,
4357                               bool IncludeDependentBases, bool LoadExternal) {
4358   LookupVisibleHelper H(Consumer, IncludeDependentBases, LoadExternal);
4359   H.lookupVisibleDecls(*this, Ctx, Kind, IncludeGlobalScope);
4360 }
4361 
4362 LabelDecl *Sema::LookupOrCreateLabel(IdentifierInfo *II, SourceLocation Loc,
4363                                      SourceLocation GnuLabelLoc) {
4364   // Do a lookup to see if we have a label with this name already.
4365   NamedDecl *Res = nullptr;
4366 
4367   if (GnuLabelLoc.isValid()) {
4368     // Local label definitions always shadow existing labels.
4369     Res = LabelDecl::Create(Context, CurContext, Loc, II, GnuLabelLoc);
4370     Scope *S = CurScope;
4371     PushOnScopeChains(Res, S, true);
4372     return cast<LabelDecl>(Res);
4373   }
4374 
4375   // Not a GNU local label.
4376   Res = LookupSingleName(CurScope, II, Loc, LookupLabel,
4377                          RedeclarationKind::NotForRedeclaration);
4378   // If we found a label, check to see if it is in the same context as us.
4379   // When in a Block, we don't want to reuse a label in an enclosing function.
4380   if (Res && Res->getDeclContext() != CurContext)
4381     Res = nullptr;
4382   if (!Res) {
4383     // If not forward referenced or defined already, create the backing decl.
4384     Res = LabelDecl::Create(Context, CurContext, Loc, II);
4385     Scope *S = CurScope->getFnParent();
4386     assert(S && "Not in a function?");
4387     PushOnScopeChains(Res, S, true);
4388   }
4389   return cast<LabelDecl>(Res);
4390 }
4391 
4392 //===----------------------------------------------------------------------===//
4393 // Typo correction
4394 //===----------------------------------------------------------------------===//
4395 
4396 static bool isCandidateViable(CorrectionCandidateCallback &CCC,
4397                               TypoCorrection &Candidate) {
4398   Candidate.setCallbackDistance(CCC.RankCandidate(Candidate));
4399   return Candidate.getEditDistance(false) != TypoCorrection::InvalidDistance;
4400 }
4401 
4402 static void LookupPotentialTypoResult(Sema &SemaRef,
4403                                       LookupResult &Res,
4404                                       IdentifierInfo *Name,
4405                                       Scope *S, CXXScopeSpec *SS,
4406                                       DeclContext *MemberContext,
4407                                       bool EnteringContext,
4408                                       bool isObjCIvarLookup,
4409                                       bool FindHidden);
4410 
4411 /// Check whether the declarations found for a typo correction are
4412 /// visible. Set the correction's RequiresImport flag to true if none of the
4413 /// declarations are visible, false otherwise.
4414 static void checkCorrectionVisibility(Sema &SemaRef, TypoCorrection &TC) {
4415   TypoCorrection::decl_iterator DI = TC.begin(), DE = TC.end();
4416 
4417   for (/**/; DI != DE; ++DI)
4418     if (!LookupResult::isVisible(SemaRef, *DI))
4419       break;
4420   // No filtering needed if all decls are visible.
4421   if (DI == DE) {
4422     TC.setRequiresImport(false);
4423     return;
4424   }
4425 
4426   llvm::SmallVector<NamedDecl*, 4> NewDecls(TC.begin(), DI);
4427   bool AnyVisibleDecls = !NewDecls.empty();
4428 
4429   for (/**/; DI != DE; ++DI) {
4430     if (LookupResult::isVisible(SemaRef, *DI)) {
4431       if (!AnyVisibleDecls) {
4432         // Found a visible decl, discard all hidden ones.
4433         AnyVisibleDecls = true;
4434         NewDecls.clear();
4435       }
4436       NewDecls.push_back(*DI);
4437     } else if (!AnyVisibleDecls && !(*DI)->isModulePrivate())
4438       NewDecls.push_back(*DI);
4439   }
4440 
4441   if (NewDecls.empty())
4442     TC = TypoCorrection();
4443   else {
4444     TC.setCorrectionDecls(NewDecls);
4445     TC.setRequiresImport(!AnyVisibleDecls);
4446   }
4447 }
4448 
4449 // Fill the supplied vector with the IdentifierInfo pointers for each piece of
4450 // the given NestedNameSpecifier (i.e. given a NestedNameSpecifier "foo::bar::",
4451 // fill the vector with the IdentifierInfo pointers for "foo" and "bar").
4452 static void getNestedNameSpecifierIdentifiers(
4453     NestedNameSpecifier *NNS,
4454     SmallVectorImpl<const IdentifierInfo*> &Identifiers) {
4455   if (NestedNameSpecifier *Prefix = NNS->getPrefix())
4456     getNestedNameSpecifierIdentifiers(Prefix, Identifiers);
4457   else
4458     Identifiers.clear();
4459 
4460   const IdentifierInfo *II = nullptr;
4461 
4462   switch (NNS->getKind()) {
4463   case NestedNameSpecifier::Identifier:
4464     II = NNS->getAsIdentifier();
4465     break;
4466 
4467   case NestedNameSpecifier::Namespace:
4468     if (NNS->getAsNamespace()->isAnonymousNamespace())
4469       return;
4470     II = NNS->getAsNamespace()->getIdentifier();
4471     break;
4472 
4473   case NestedNameSpecifier::NamespaceAlias:
4474     II = NNS->getAsNamespaceAlias()->getIdentifier();
4475     break;
4476 
4477   case NestedNameSpecifier::TypeSpecWithTemplate:
4478   case NestedNameSpecifier::TypeSpec:
4479     II = QualType(NNS->getAsType(), 0).getBaseTypeIdentifier();
4480     break;
4481 
4482   case NestedNameSpecifier::Global:
4483   case NestedNameSpecifier::Super:
4484     return;
4485   }
4486 
4487   if (II)
4488     Identifiers.push_back(II);
4489 }
4490 
4491 void TypoCorrectionConsumer::FoundDecl(NamedDecl *ND, NamedDecl *Hiding,
4492                                        DeclContext *Ctx, bool InBaseClass) {
4493   // Don't consider hidden names for typo correction.
4494   if (Hiding)
4495     return;
4496 
4497   // Only consider entities with identifiers for names, ignoring
4498   // special names (constructors, overloaded operators, selectors,
4499   // etc.).
4500   IdentifierInfo *Name = ND->getIdentifier();
4501   if (!Name)
4502     return;
4503 
4504   // Only consider visible declarations and declarations from modules with
4505   // names that exactly match.
4506   if (!LookupResult::isVisible(SemaRef, ND) && Name != Typo)
4507     return;
4508 
4509   FoundName(Name->getName());
4510 }
4511 
4512 void TypoCorrectionConsumer::FoundName(StringRef Name) {
4513   // Compute the edit distance between the typo and the name of this
4514   // entity, and add the identifier to the list of results.
4515   addName(Name, nullptr);
4516 }
4517 
4518 void TypoCorrectionConsumer::addKeywordResult(StringRef Keyword) {
4519   // Compute the edit distance between the typo and this keyword,
4520   // and add the keyword to the list of results.
4521   addName(Keyword, nullptr, nullptr, true);
4522 }
4523 
4524 void TypoCorrectionConsumer::addName(StringRef Name, NamedDecl *ND,
4525                                      NestedNameSpecifier *NNS, bool isKeyword) {
4526   // Use a simple length-based heuristic to determine the minimum possible
4527   // edit distance. If the minimum isn't good enough, bail out early.
4528   StringRef TypoStr = Typo->getName();
4529   unsigned MinED = abs((int)Name.size() - (int)TypoStr.size());
4530   if (MinED && TypoStr.size() / MinED < 3)
4531     return;
4532 
4533   // Compute an upper bound on the allowable edit distance, so that the
4534   // edit-distance algorithm can short-circuit.
4535   unsigned UpperBound = (TypoStr.size() + 2) / 3;
4536   unsigned ED = TypoStr.edit_distance(Name, true, UpperBound);
4537   if (ED > UpperBound) return;
4538 
4539   TypoCorrection TC(&SemaRef.Context.Idents.get(Name), ND, NNS, ED);
4540   if (isKeyword) TC.makeKeyword();
4541   TC.setCorrectionRange(nullptr, Result.getLookupNameInfo());
4542   addCorrection(TC);
4543 }
4544 
4545 static const unsigned MaxTypoDistanceResultSets = 5;
4546 
4547 void TypoCorrectionConsumer::addCorrection(TypoCorrection Correction) {
4548   StringRef TypoStr = Typo->getName();
4549   StringRef Name = Correction.getCorrectionAsIdentifierInfo()->getName();
4550 
4551   // For very short typos, ignore potential corrections that have a different
4552   // base identifier from the typo or which have a normalized edit distance
4553   // longer than the typo itself.
4554   if (TypoStr.size() < 3 &&
4555       (Name != TypoStr || Correction.getEditDistance(true) > TypoStr.size()))
4556     return;
4557 
4558   // If the correction is resolved but is not viable, ignore it.
4559   if (Correction.isResolved()) {
4560     checkCorrectionVisibility(SemaRef, Correction);
4561     if (!Correction || !isCandidateViable(*CorrectionValidator, Correction))
4562       return;
4563   }
4564 
4565   TypoResultList &CList =
4566       CorrectionResults[Correction.getEditDistance(false)][Name];
4567 
4568   if (!CList.empty() && !CList.back().isResolved())
4569     CList.pop_back();
4570   if (NamedDecl *NewND = Correction.getCorrectionDecl()) {
4571     auto RI = llvm::find_if(CList, [NewND](const TypoCorrection &TypoCorr) {
4572       return TypoCorr.getCorrectionDecl() == NewND;
4573     });
4574     if (RI != CList.end()) {
4575       // The Correction refers to a decl already in the list. No insertion is
4576       // necessary and all further cases will return.
4577 
4578       auto IsDeprecated = [](Decl *D) {
4579         while (D) {
4580           if (D->isDeprecated())
4581             return true;
4582           D = llvm::dyn_cast_or_null<NamespaceDecl>(D->getDeclContext());
4583         }
4584         return false;
4585       };
4586 
4587       // Prefer non deprecated Corrections over deprecated and only then
4588       // sort using an alphabetical order.
4589       std::pair<bool, std::string> NewKey = {
4590           IsDeprecated(Correction.getFoundDecl()),
4591           Correction.getAsString(SemaRef.getLangOpts())};
4592 
4593       std::pair<bool, std::string> PrevKey = {
4594           IsDeprecated(RI->getFoundDecl()),
4595           RI->getAsString(SemaRef.getLangOpts())};
4596 
4597       if (NewKey < PrevKey)
4598         *RI = Correction;
4599       return;
4600     }
4601   }
4602   if (CList.empty() || Correction.isResolved())
4603     CList.push_back(Correction);
4604 
4605   while (CorrectionResults.size() > MaxTypoDistanceResultSets)
4606     CorrectionResults.erase(std::prev(CorrectionResults.end()));
4607 }
4608 
4609 void TypoCorrectionConsumer::addNamespaces(
4610     const llvm::MapVector<NamespaceDecl *, bool> &KnownNamespaces) {
4611   SearchNamespaces = true;
4612 
4613   for (auto KNPair : KnownNamespaces)
4614     Namespaces.addNameSpecifier(KNPair.first);
4615 
4616   bool SSIsTemplate = false;
4617   if (NestedNameSpecifier *NNS =
4618           (SS && SS->isValid()) ? SS->getScopeRep() : nullptr) {
4619     if (const Type *T = NNS->getAsType())
4620       SSIsTemplate = T->getTypeClass() == Type::TemplateSpecialization;
4621   }
4622   // Do not transform this into an iterator-based loop. The loop body can
4623   // trigger the creation of further types (through lazy deserialization) and
4624   // invalid iterators into this list.
4625   auto &Types = SemaRef.getASTContext().getTypes();
4626   for (unsigned I = 0; I != Types.size(); ++I) {
4627     const auto *TI = Types[I];
4628     if (CXXRecordDecl *CD = TI->getAsCXXRecordDecl()) {
4629       CD = CD->getCanonicalDecl();
4630       if (!CD->isDependentType() && !CD->isAnonymousStructOrUnion() &&
4631           !CD->isUnion() && CD->getIdentifier() &&
4632           (SSIsTemplate || !isa<ClassTemplateSpecializationDecl>(CD)) &&
4633           (CD->isBeingDefined() || CD->isCompleteDefinition()))
4634         Namespaces.addNameSpecifier(CD);
4635     }
4636   }
4637 }
4638 
4639 const TypoCorrection &TypoCorrectionConsumer::getNextCorrection() {
4640   if (++CurrentTCIndex < ValidatedCorrections.size())
4641     return ValidatedCorrections[CurrentTCIndex];
4642 
4643   CurrentTCIndex = ValidatedCorrections.size();
4644   while (!CorrectionResults.empty()) {
4645     auto DI = CorrectionResults.begin();
4646     if (DI->second.empty()) {
4647       CorrectionResults.erase(DI);
4648       continue;
4649     }
4650 
4651     auto RI = DI->second.begin();
4652     if (RI->second.empty()) {
4653       DI->second.erase(RI);
4654       performQualifiedLookups();
4655       continue;
4656     }
4657 
4658     TypoCorrection TC = RI->second.pop_back_val();
4659     if (TC.isResolved() || TC.requiresImport() || resolveCorrection(TC)) {
4660       ValidatedCorrections.push_back(TC);
4661       return ValidatedCorrections[CurrentTCIndex];
4662     }
4663   }
4664   return ValidatedCorrections[0];  // The empty correction.
4665 }
4666 
4667 bool TypoCorrectionConsumer::resolveCorrection(TypoCorrection &Candidate) {
4668   IdentifierInfo *Name = Candidate.getCorrectionAsIdentifierInfo();
4669   DeclContext *TempMemberContext = MemberContext;
4670   CXXScopeSpec *TempSS = SS.get();
4671 retry_lookup:
4672   LookupPotentialTypoResult(SemaRef, Result, Name, S, TempSS, TempMemberContext,
4673                             EnteringContext,
4674                             CorrectionValidator->IsObjCIvarLookup,
4675                             Name == Typo && !Candidate.WillReplaceSpecifier());
4676   switch (Result.getResultKind()) {
4677   case LookupResult::NotFound:
4678   case LookupResult::NotFoundInCurrentInstantiation:
4679   case LookupResult::FoundUnresolvedValue:
4680     if (TempSS) {
4681       // Immediately retry the lookup without the given CXXScopeSpec
4682       TempSS = nullptr;
4683       Candidate.WillReplaceSpecifier(true);
4684       goto retry_lookup;
4685     }
4686     if (TempMemberContext) {
4687       if (SS && !TempSS)
4688         TempSS = SS.get();
4689       TempMemberContext = nullptr;
4690       goto retry_lookup;
4691     }
4692     if (SearchNamespaces)
4693       QualifiedResults.push_back(Candidate);
4694     break;
4695 
4696   case LookupResult::Ambiguous:
4697     // We don't deal with ambiguities.
4698     break;
4699 
4700   case LookupResult::Found:
4701   case LookupResult::FoundOverloaded:
4702     // Store all of the Decls for overloaded symbols
4703     for (auto *TRD : Result)
4704       Candidate.addCorrectionDecl(TRD);
4705     checkCorrectionVisibility(SemaRef, Candidate);
4706     if (!isCandidateViable(*CorrectionValidator, Candidate)) {
4707       if (SearchNamespaces)
4708         QualifiedResults.push_back(Candidate);
4709       break;
4710     }
4711     Candidate.setCorrectionRange(SS.get(), Result.getLookupNameInfo());
4712     return true;
4713   }
4714   return false;
4715 }
4716 
4717 void TypoCorrectionConsumer::performQualifiedLookups() {
4718   unsigned TypoLen = Typo->getName().size();
4719   for (const TypoCorrection &QR : QualifiedResults) {
4720     for (const auto &NSI : Namespaces) {
4721       DeclContext *Ctx = NSI.DeclCtx;
4722       const Type *NSType = NSI.NameSpecifier->getAsType();
4723 
4724       // If the current NestedNameSpecifier refers to a class and the
4725       // current correction candidate is the name of that class, then skip
4726       // it as it is unlikely a qualified version of the class' constructor
4727       // is an appropriate correction.
4728       if (CXXRecordDecl *NSDecl = NSType ? NSType->getAsCXXRecordDecl() :
4729                                            nullptr) {
4730         if (NSDecl->getIdentifier() == QR.getCorrectionAsIdentifierInfo())
4731           continue;
4732       }
4733 
4734       TypoCorrection TC(QR);
4735       TC.ClearCorrectionDecls();
4736       TC.setCorrectionSpecifier(NSI.NameSpecifier);
4737       TC.setQualifierDistance(NSI.EditDistance);
4738       TC.setCallbackDistance(0); // Reset the callback distance
4739 
4740       // If the current correction candidate and namespace combination are
4741       // too far away from the original typo based on the normalized edit
4742       // distance, then skip performing a qualified name lookup.
4743       unsigned TmpED = TC.getEditDistance(true);
4744       if (QR.getCorrectionAsIdentifierInfo() != Typo && TmpED &&
4745           TypoLen / TmpED < 3)
4746         continue;
4747 
4748       Result.clear();
4749       Result.setLookupName(QR.getCorrectionAsIdentifierInfo());
4750       if (!SemaRef.LookupQualifiedName(Result, Ctx))
4751         continue;
4752 
4753       // Any corrections added below will be validated in subsequent
4754       // iterations of the main while() loop over the Consumer's contents.
4755       switch (Result.getResultKind()) {
4756       case LookupResult::Found:
4757       case LookupResult::FoundOverloaded: {
4758         if (SS && SS->isValid()) {
4759           std::string NewQualified = TC.getAsString(SemaRef.getLangOpts());
4760           std::string OldQualified;
4761           llvm::raw_string_ostream OldOStream(OldQualified);
4762           SS->getScopeRep()->print(OldOStream, SemaRef.getPrintingPolicy());
4763           OldOStream << Typo->getName();
4764           // If correction candidate would be an identical written qualified
4765           // identifier, then the existing CXXScopeSpec probably included a
4766           // typedef that didn't get accounted for properly.
4767           if (OldOStream.str() == NewQualified)
4768             break;
4769         }
4770         for (LookupResult::iterator TRD = Result.begin(), TRDEnd = Result.end();
4771              TRD != TRDEnd; ++TRD) {
4772           if (SemaRef.CheckMemberAccess(TC.getCorrectionRange().getBegin(),
4773                                         NSType ? NSType->getAsCXXRecordDecl()
4774                                                : nullptr,
4775                                         TRD.getPair()) == Sema::AR_accessible)
4776             TC.addCorrectionDecl(*TRD);
4777         }
4778         if (TC.isResolved()) {
4779           TC.setCorrectionRange(SS.get(), Result.getLookupNameInfo());
4780           addCorrection(TC);
4781         }
4782         break;
4783       }
4784       case LookupResult::NotFound:
4785       case LookupResult::NotFoundInCurrentInstantiation:
4786       case LookupResult::Ambiguous:
4787       case LookupResult::FoundUnresolvedValue:
4788         break;
4789       }
4790     }
4791   }
4792   QualifiedResults.clear();
4793 }
4794 
4795 TypoCorrectionConsumer::NamespaceSpecifierSet::NamespaceSpecifierSet(
4796     ASTContext &Context, DeclContext *CurContext, CXXScopeSpec *CurScopeSpec)
4797     : Context(Context), CurContextChain(buildContextChain(CurContext)) {
4798   if (NestedNameSpecifier *NNS =
4799           CurScopeSpec ? CurScopeSpec->getScopeRep() : nullptr) {
4800     llvm::raw_string_ostream SpecifierOStream(CurNameSpecifier);
4801     NNS->print(SpecifierOStream, Context.getPrintingPolicy());
4802 
4803     getNestedNameSpecifierIdentifiers(NNS, CurNameSpecifierIdentifiers);
4804   }
4805   // Build the list of identifiers that would be used for an absolute
4806   // (from the global context) NestedNameSpecifier referring to the current
4807   // context.
4808   for (DeclContext *C : llvm::reverse(CurContextChain)) {
4809     if (auto *ND = dyn_cast_or_null<NamespaceDecl>(C))
4810       CurContextIdentifiers.push_back(ND->getIdentifier());
4811   }
4812 
4813   // Add the global context as a NestedNameSpecifier
4814   SpecifierInfo SI = {cast<DeclContext>(Context.getTranslationUnitDecl()),
4815                       NestedNameSpecifier::GlobalSpecifier(Context), 1};
4816   DistanceMap[1].push_back(SI);
4817 }
4818 
4819 auto TypoCorrectionConsumer::NamespaceSpecifierSet::buildContextChain(
4820     DeclContext *Start) -> DeclContextList {
4821   assert(Start && "Building a context chain from a null context");
4822   DeclContextList Chain;
4823   for (DeclContext *DC = Start->getPrimaryContext(); DC != nullptr;
4824        DC = DC->getLookupParent()) {
4825     NamespaceDecl *ND = dyn_cast_or_null<NamespaceDecl>(DC);
4826     if (!DC->isInlineNamespace() && !DC->isTransparentContext() &&
4827         !(ND && ND->isAnonymousNamespace()))
4828       Chain.push_back(DC->getPrimaryContext());
4829   }
4830   return Chain;
4831 }
4832 
4833 unsigned
4834 TypoCorrectionConsumer::NamespaceSpecifierSet::buildNestedNameSpecifier(
4835     DeclContextList &DeclChain, NestedNameSpecifier *&NNS) {
4836   unsigned NumSpecifiers = 0;
4837   for (DeclContext *C : llvm::reverse(DeclChain)) {
4838     if (auto *ND = dyn_cast_or_null<NamespaceDecl>(C)) {
4839       NNS = NestedNameSpecifier::Create(Context, NNS, ND);
4840       ++NumSpecifiers;
4841     } else if (auto *RD = dyn_cast_or_null<RecordDecl>(C)) {
4842       NNS = NestedNameSpecifier::Create(Context, NNS, RD->isTemplateDecl(),
4843                                         RD->getTypeForDecl());
4844       ++NumSpecifiers;
4845     }
4846   }
4847   return NumSpecifiers;
4848 }
4849 
4850 void TypoCorrectionConsumer::NamespaceSpecifierSet::addNameSpecifier(
4851     DeclContext *Ctx) {
4852   NestedNameSpecifier *NNS = nullptr;
4853   unsigned NumSpecifiers = 0;
4854   DeclContextList NamespaceDeclChain(buildContextChain(Ctx));
4855   DeclContextList FullNamespaceDeclChain(NamespaceDeclChain);
4856 
4857   // Eliminate common elements from the two DeclContext chains.
4858   for (DeclContext *C : llvm::reverse(CurContextChain)) {
4859     if (NamespaceDeclChain.empty() || NamespaceDeclChain.back() != C)
4860       break;
4861     NamespaceDeclChain.pop_back();
4862   }
4863 
4864   // Build the NestedNameSpecifier from what is left of the NamespaceDeclChain
4865   NumSpecifiers = buildNestedNameSpecifier(NamespaceDeclChain, NNS);
4866 
4867   // Add an explicit leading '::' specifier if needed.
4868   if (NamespaceDeclChain.empty()) {
4869     // Rebuild the NestedNameSpecifier as a globally-qualified specifier.
4870     NNS = NestedNameSpecifier::GlobalSpecifier(Context);
4871     NumSpecifiers =
4872         buildNestedNameSpecifier(FullNamespaceDeclChain, NNS);
4873   } else if (NamedDecl *ND =
4874                  dyn_cast_or_null<NamedDecl>(NamespaceDeclChain.back())) {
4875     IdentifierInfo *Name = ND->getIdentifier();
4876     bool SameNameSpecifier = false;
4877     if (llvm::is_contained(CurNameSpecifierIdentifiers, Name)) {
4878       std::string NewNameSpecifier;
4879       llvm::raw_string_ostream SpecifierOStream(NewNameSpecifier);
4880       SmallVector<const IdentifierInfo *, 4> NewNameSpecifierIdentifiers;
4881       getNestedNameSpecifierIdentifiers(NNS, NewNameSpecifierIdentifiers);
4882       NNS->print(SpecifierOStream, Context.getPrintingPolicy());
4883       SpecifierOStream.flush();
4884       SameNameSpecifier = NewNameSpecifier == CurNameSpecifier;
4885     }
4886     if (SameNameSpecifier || llvm::is_contained(CurContextIdentifiers, Name)) {
4887       // Rebuild the NestedNameSpecifier as a globally-qualified specifier.
4888       NNS = NestedNameSpecifier::GlobalSpecifier(Context);
4889       NumSpecifiers =
4890           buildNestedNameSpecifier(FullNamespaceDeclChain, NNS);
4891     }
4892   }
4893 
4894   // If the built NestedNameSpecifier would be replacing an existing
4895   // NestedNameSpecifier, use the number of component identifiers that
4896   // would need to be changed as the edit distance instead of the number
4897   // of components in the built NestedNameSpecifier.
4898   if (NNS && !CurNameSpecifierIdentifiers.empty()) {
4899     SmallVector<const IdentifierInfo*, 4> NewNameSpecifierIdentifiers;
4900     getNestedNameSpecifierIdentifiers(NNS, NewNameSpecifierIdentifiers);
4901     NumSpecifiers =
4902         llvm::ComputeEditDistance(llvm::ArrayRef(CurNameSpecifierIdentifiers),
4903                                   llvm::ArrayRef(NewNameSpecifierIdentifiers));
4904   }
4905 
4906   SpecifierInfo SI = {Ctx, NNS, NumSpecifiers};
4907   DistanceMap[NumSpecifiers].push_back(SI);
4908 }
4909 
4910 /// Perform name lookup for a possible result for typo correction.
4911 static void LookupPotentialTypoResult(Sema &SemaRef,
4912                                       LookupResult &Res,
4913                                       IdentifierInfo *Name,
4914                                       Scope *S, CXXScopeSpec *SS,
4915                                       DeclContext *MemberContext,
4916                                       bool EnteringContext,
4917                                       bool isObjCIvarLookup,
4918                                       bool FindHidden) {
4919   Res.suppressDiagnostics();
4920   Res.clear();
4921   Res.setLookupName(Name);
4922   Res.setAllowHidden(FindHidden);
4923   if (MemberContext) {
4924     if (ObjCInterfaceDecl *Class = dyn_cast<ObjCInterfaceDecl>(MemberContext)) {
4925       if (isObjCIvarLookup) {
4926         if (ObjCIvarDecl *Ivar = Class->lookupInstanceVariable(Name)) {
4927           Res.addDecl(Ivar);
4928           Res.resolveKind();
4929           return;
4930         }
4931       }
4932 
4933       if (ObjCPropertyDecl *Prop = Class->FindPropertyDeclaration(
4934               Name, ObjCPropertyQueryKind::OBJC_PR_query_instance)) {
4935         Res.addDecl(Prop);
4936         Res.resolveKind();
4937         return;
4938       }
4939     }
4940 
4941     SemaRef.LookupQualifiedName(Res, MemberContext);
4942     return;
4943   }
4944 
4945   SemaRef.LookupParsedName(Res, S, SS,
4946                            /*ObjectType=*/QualType(),
4947                            /*AllowBuiltinCreation=*/false, EnteringContext);
4948 
4949   // Fake ivar lookup; this should really be part of
4950   // LookupParsedName.
4951   if (ObjCMethodDecl *Method = SemaRef.getCurMethodDecl()) {
4952     if (Method->isInstanceMethod() && Method->getClassInterface() &&
4953         (Res.empty() ||
4954          (Res.isSingleResult() &&
4955           Res.getFoundDecl()->isDefinedOutsideFunctionOrMethod()))) {
4956        if (ObjCIvarDecl *IV
4957              = Method->getClassInterface()->lookupInstanceVariable(Name)) {
4958          Res.addDecl(IV);
4959          Res.resolveKind();
4960        }
4961      }
4962   }
4963 }
4964 
4965 /// Add keywords to the consumer as possible typo corrections.
4966 static void AddKeywordsToConsumer(Sema &SemaRef,
4967                                   TypoCorrectionConsumer &Consumer,
4968                                   Scope *S, CorrectionCandidateCallback &CCC,
4969                                   bool AfterNestedNameSpecifier) {
4970   if (AfterNestedNameSpecifier) {
4971     // For 'X::', we know exactly which keywords can appear next.
4972     Consumer.addKeywordResult("template");
4973     if (CCC.WantExpressionKeywords)
4974       Consumer.addKeywordResult("operator");
4975     return;
4976   }
4977 
4978   if (CCC.WantObjCSuper)
4979     Consumer.addKeywordResult("super");
4980 
4981   if (CCC.WantTypeSpecifiers) {
4982     // Add type-specifier keywords to the set of results.
4983     static const char *const CTypeSpecs[] = {
4984       "char", "const", "double", "enum", "float", "int", "long", "short",
4985       "signed", "struct", "union", "unsigned", "void", "volatile",
4986       "_Complex",
4987       // storage-specifiers as well
4988       "extern", "inline", "static", "typedef"
4989     };
4990 
4991     for (const auto *CTS : CTypeSpecs)
4992       Consumer.addKeywordResult(CTS);
4993 
4994     if (SemaRef.getLangOpts().C99 && !SemaRef.getLangOpts().C2y)
4995       Consumer.addKeywordResult("_Imaginary");
4996 
4997     if (SemaRef.getLangOpts().C99)
4998       Consumer.addKeywordResult("restrict");
4999     if (SemaRef.getLangOpts().Bool || SemaRef.getLangOpts().CPlusPlus)
5000       Consumer.addKeywordResult("bool");
5001     else if (SemaRef.getLangOpts().C99)
5002       Consumer.addKeywordResult("_Bool");
5003 
5004     if (SemaRef.getLangOpts().CPlusPlus) {
5005       Consumer.addKeywordResult("class");
5006       Consumer.addKeywordResult("typename");
5007       Consumer.addKeywordResult("wchar_t");
5008 
5009       if (SemaRef.getLangOpts().CPlusPlus11) {
5010         Consumer.addKeywordResult("char16_t");
5011         Consumer.addKeywordResult("char32_t");
5012         Consumer.addKeywordResult("constexpr");
5013         Consumer.addKeywordResult("decltype");
5014         Consumer.addKeywordResult("thread_local");
5015       }
5016     }
5017 
5018     if (SemaRef.getLangOpts().GNUKeywords)
5019       Consumer.addKeywordResult("typeof");
5020   } else if (CCC.WantFunctionLikeCasts) {
5021     static const char *const CastableTypeSpecs[] = {
5022       "char", "double", "float", "int", "long", "short",
5023       "signed", "unsigned", "void"
5024     };
5025     for (auto *kw : CastableTypeSpecs)
5026       Consumer.addKeywordResult(kw);
5027   }
5028 
5029   if (CCC.WantCXXNamedCasts && SemaRef.getLangOpts().CPlusPlus) {
5030     Consumer.addKeywordResult("const_cast");
5031     Consumer.addKeywordResult("dynamic_cast");
5032     Consumer.addKeywordResult("reinterpret_cast");
5033     Consumer.addKeywordResult("static_cast");
5034   }
5035 
5036   if (CCC.WantExpressionKeywords) {
5037     Consumer.addKeywordResult("sizeof");
5038     if (SemaRef.getLangOpts().Bool || SemaRef.getLangOpts().CPlusPlus) {
5039       Consumer.addKeywordResult("false");
5040       Consumer.addKeywordResult("true");
5041     }
5042 
5043     if (SemaRef.getLangOpts().CPlusPlus) {
5044       static const char *const CXXExprs[] = {
5045         "delete", "new", "operator", "throw", "typeid"
5046       };
5047       for (const auto *CE : CXXExprs)
5048         Consumer.addKeywordResult(CE);
5049 
5050       if (isa<CXXMethodDecl>(SemaRef.CurContext) &&
5051           cast<CXXMethodDecl>(SemaRef.CurContext)->isInstance())
5052         Consumer.addKeywordResult("this");
5053 
5054       if (SemaRef.getLangOpts().CPlusPlus11) {
5055         Consumer.addKeywordResult("alignof");
5056         Consumer.addKeywordResult("nullptr");
5057       }
5058     }
5059 
5060     if (SemaRef.getLangOpts().C11) {
5061       // FIXME: We should not suggest _Alignof if the alignof macro
5062       // is present.
5063       Consumer.addKeywordResult("_Alignof");
5064     }
5065   }
5066 
5067   if (CCC.WantRemainingKeywords) {
5068     if (SemaRef.getCurFunctionOrMethodDecl() || SemaRef.getCurBlock()) {
5069       // Statements.
5070       static const char *const CStmts[] = {
5071         "do", "else", "for", "goto", "if", "return", "switch", "while" };
5072       for (const auto *CS : CStmts)
5073         Consumer.addKeywordResult(CS);
5074 
5075       if (SemaRef.getLangOpts().CPlusPlus) {
5076         Consumer.addKeywordResult("catch");
5077         Consumer.addKeywordResult("try");
5078       }
5079 
5080       if (S && S->getBreakParent())
5081         Consumer.addKeywordResult("break");
5082 
5083       if (S && S->getContinueParent())
5084         Consumer.addKeywordResult("continue");
5085 
5086       if (SemaRef.getCurFunction() &&
5087           !SemaRef.getCurFunction()->SwitchStack.empty()) {
5088         Consumer.addKeywordResult("case");
5089         Consumer.addKeywordResult("default");
5090       }
5091     } else {
5092       if (SemaRef.getLangOpts().CPlusPlus) {
5093         Consumer.addKeywordResult("namespace");
5094         Consumer.addKeywordResult("template");
5095       }
5096 
5097       if (S && S->isClassScope()) {
5098         Consumer.addKeywordResult("explicit");
5099         Consumer.addKeywordResult("friend");
5100         Consumer.addKeywordResult("mutable");
5101         Consumer.addKeywordResult("private");
5102         Consumer.addKeywordResult("protected");
5103         Consumer.addKeywordResult("public");
5104         Consumer.addKeywordResult("virtual");
5105       }
5106     }
5107 
5108     if (SemaRef.getLangOpts().CPlusPlus) {
5109       Consumer.addKeywordResult("using");
5110 
5111       if (SemaRef.getLangOpts().CPlusPlus11)
5112         Consumer.addKeywordResult("static_assert");
5113     }
5114   }
5115 }
5116 
5117 std::unique_ptr<TypoCorrectionConsumer> Sema::makeTypoCorrectionConsumer(
5118     const DeclarationNameInfo &TypoName, Sema::LookupNameKind LookupKind,
5119     Scope *S, CXXScopeSpec *SS, CorrectionCandidateCallback &CCC,
5120     DeclContext *MemberContext, bool EnteringContext,
5121     const ObjCObjectPointerType *OPT, bool ErrorRecovery) {
5122 
5123   if (Diags.hasFatalErrorOccurred() || !getLangOpts().SpellChecking ||
5124       DisableTypoCorrection)
5125     return nullptr;
5126 
5127   // In Microsoft mode, don't perform typo correction in a template member
5128   // function dependent context because it interferes with the "lookup into
5129   // dependent bases of class templates" feature.
5130   if (getLangOpts().MSVCCompat && CurContext->isDependentContext() &&
5131       isa<CXXMethodDecl>(CurContext))
5132     return nullptr;
5133 
5134   // We only attempt to correct typos for identifiers.
5135   IdentifierInfo *Typo = TypoName.getName().getAsIdentifierInfo();
5136   if (!Typo)
5137     return nullptr;
5138 
5139   // If the scope specifier itself was invalid, don't try to correct
5140   // typos.
5141   if (SS && SS->isInvalid())
5142     return nullptr;
5143 
5144   // Never try to correct typos during any kind of code synthesis.
5145   if (!CodeSynthesisContexts.empty())
5146     return nullptr;
5147 
5148   // Don't try to correct 'super'.
5149   if (S && S->isInObjcMethodScope() && Typo == getSuperIdentifier())
5150     return nullptr;
5151 
5152   // Abort if typo correction already failed for this specific typo.
5153   IdentifierSourceLocations::iterator locs = TypoCorrectionFailures.find(Typo);
5154   if (locs != TypoCorrectionFailures.end() &&
5155       locs->second.count(TypoName.getLoc()))
5156     return nullptr;
5157 
5158   // Don't try to correct the identifier "vector" when in AltiVec mode.
5159   // TODO: Figure out why typo correction misbehaves in this case, fix it, and
5160   // remove this workaround.
5161   if ((getLangOpts().AltiVec || getLangOpts().ZVector) && Typo->isStr("vector"))
5162     return nullptr;
5163 
5164   // Provide a stop gap for files that are just seriously broken.  Trying
5165   // to correct all typos can turn into a HUGE performance penalty, causing
5166   // some files to take minutes to get rejected by the parser.
5167   unsigned Limit = getDiagnostics().getDiagnosticOptions().SpellCheckingLimit;
5168   if (Limit && TyposCorrected >= Limit)
5169     return nullptr;
5170   ++TyposCorrected;
5171 
5172   // If we're handling a missing symbol error, using modules, and the
5173   // special search all modules option is used, look for a missing import.
5174   if (ErrorRecovery && getLangOpts().Modules &&
5175       getLangOpts().ModulesSearchAll) {
5176     // The following has the side effect of loading the missing module.
5177     getModuleLoader().lookupMissingImports(Typo->getName(),
5178                                            TypoName.getBeginLoc());
5179   }
5180 
5181   // Extend the lifetime of the callback. We delayed this until here
5182   // to avoid allocations in the hot path (which is where no typo correction
5183   // occurs). Note that CorrectionCandidateCallback is polymorphic and
5184   // initially stack-allocated.
5185   std::unique_ptr<CorrectionCandidateCallback> ClonedCCC = CCC.clone();
5186   auto Consumer = std::make_unique<TypoCorrectionConsumer>(
5187       *this, TypoName, LookupKind, S, SS, std::move(ClonedCCC), MemberContext,
5188       EnteringContext);
5189 
5190   // Perform name lookup to find visible, similarly-named entities.
5191   bool IsUnqualifiedLookup = false;
5192   DeclContext *QualifiedDC = MemberContext;
5193   if (MemberContext) {
5194     LookupVisibleDecls(MemberContext, LookupKind, *Consumer);
5195 
5196     // Look in qualified interfaces.
5197     if (OPT) {
5198       for (auto *I : OPT->quals())
5199         LookupVisibleDecls(I, LookupKind, *Consumer);
5200     }
5201   } else if (SS && SS->isSet()) {
5202     QualifiedDC = computeDeclContext(*SS, EnteringContext);
5203     if (!QualifiedDC)
5204       return nullptr;
5205 
5206     LookupVisibleDecls(QualifiedDC, LookupKind, *Consumer);
5207   } else {
5208     IsUnqualifiedLookup = true;
5209   }
5210 
5211   // Determine whether we are going to search in the various namespaces for
5212   // corrections.
5213   bool SearchNamespaces
5214     = getLangOpts().CPlusPlus &&
5215       (IsUnqualifiedLookup || (SS && SS->isSet()));
5216 
5217   if (IsUnqualifiedLookup || SearchNamespaces) {
5218     // For unqualified lookup, look through all of the names that we have
5219     // seen in this translation unit.
5220     // FIXME: Re-add the ability to skip very unlikely potential corrections.
5221     for (const auto &I : Context.Idents)
5222       Consumer->FoundName(I.getKey());
5223 
5224     // Walk through identifiers in external identifier sources.
5225     // FIXME: Re-add the ability to skip very unlikely potential corrections.
5226     if (IdentifierInfoLookup *External
5227                             = Context.Idents.getExternalIdentifierLookup()) {
5228       std::unique_ptr<IdentifierIterator> Iter(External->getIdentifiers());
5229       do {
5230         StringRef Name = Iter->Next();
5231         if (Name.empty())
5232           break;
5233 
5234         Consumer->FoundName(Name);
5235       } while (true);
5236     }
5237   }
5238 
5239   AddKeywordsToConsumer(*this, *Consumer, S,
5240                         *Consumer->getCorrectionValidator(),
5241                         SS && SS->isNotEmpty());
5242 
5243   // Build the NestedNameSpecifiers for the KnownNamespaces, if we're going
5244   // to search those namespaces.
5245   if (SearchNamespaces) {
5246     // Load any externally-known namespaces.
5247     if (ExternalSource && !LoadedExternalKnownNamespaces) {
5248       SmallVector<NamespaceDecl *, 4> ExternalKnownNamespaces;
5249       LoadedExternalKnownNamespaces = true;
5250       ExternalSource->ReadKnownNamespaces(ExternalKnownNamespaces);
5251       for (auto *N : ExternalKnownNamespaces)
5252         KnownNamespaces[N] = true;
5253     }
5254 
5255     Consumer->addNamespaces(KnownNamespaces);
5256   }
5257 
5258   return Consumer;
5259 }
5260 
5261 TypoCorrection Sema::CorrectTypo(const DeclarationNameInfo &TypoName,
5262                                  Sema::LookupNameKind LookupKind,
5263                                  Scope *S, CXXScopeSpec *SS,
5264                                  CorrectionCandidateCallback &CCC,
5265                                  CorrectTypoKind Mode,
5266                                  DeclContext *MemberContext,
5267                                  bool EnteringContext,
5268                                  const ObjCObjectPointerType *OPT,
5269                                  bool RecordFailure) {
5270   // Always let the ExternalSource have the first chance at correction, even
5271   // if we would otherwise have given up.
5272   if (ExternalSource) {
5273     if (TypoCorrection Correction =
5274             ExternalSource->CorrectTypo(TypoName, LookupKind, S, SS, CCC,
5275                                         MemberContext, EnteringContext, OPT))
5276       return Correction;
5277   }
5278 
5279   // Ugly hack equivalent to CTC == CTC_ObjCMessageReceiver;
5280   // WantObjCSuper is only true for CTC_ObjCMessageReceiver and for
5281   // some instances of CTC_Unknown, while WantRemainingKeywords is true
5282   // for CTC_Unknown but not for CTC_ObjCMessageReceiver.
5283   bool ObjCMessageReceiver = CCC.WantObjCSuper && !CCC.WantRemainingKeywords;
5284 
5285   IdentifierInfo *Typo = TypoName.getName().getAsIdentifierInfo();
5286   auto Consumer = makeTypoCorrectionConsumer(TypoName, LookupKind, S, SS, CCC,
5287                                              MemberContext, EnteringContext,
5288                                              OPT, Mode == CTK_ErrorRecovery);
5289 
5290   if (!Consumer)
5291     return TypoCorrection();
5292 
5293   // If we haven't found anything, we're done.
5294   if (Consumer->empty())
5295     return FailedCorrection(Typo, TypoName.getLoc(), RecordFailure);
5296 
5297   // Make sure the best edit distance (prior to adding any namespace qualifiers)
5298   // is not more that about a third of the length of the typo's identifier.
5299   unsigned ED = Consumer->getBestEditDistance(true);
5300   unsigned TypoLen = Typo->getName().size();
5301   if (ED > 0 && TypoLen / ED < 3)
5302     return FailedCorrection(Typo, TypoName.getLoc(), RecordFailure);
5303 
5304   TypoCorrection BestTC = Consumer->getNextCorrection();
5305   TypoCorrection SecondBestTC = Consumer->getNextCorrection();
5306   if (!BestTC)
5307     return FailedCorrection(Typo, TypoName.getLoc(), RecordFailure);
5308 
5309   ED = BestTC.getEditDistance();
5310 
5311   if (TypoLen >= 3 && ED > 0 && TypoLen / ED < 3) {
5312     // If this was an unqualified lookup and we believe the callback
5313     // object wouldn't have filtered out possible corrections, note
5314     // that no correction was found.
5315     return FailedCorrection(Typo, TypoName.getLoc(), RecordFailure);
5316   }
5317 
5318   // If only a single name remains, return that result.
5319   if (!SecondBestTC ||
5320       SecondBestTC.getEditDistance(false) > BestTC.getEditDistance(false)) {
5321     const TypoCorrection &Result = BestTC;
5322 
5323     // Don't correct to a keyword that's the same as the typo; the keyword
5324     // wasn't actually in scope.
5325     if (ED == 0 && Result.isKeyword())
5326       return FailedCorrection(Typo, TypoName.getLoc(), RecordFailure);
5327 
5328     TypoCorrection TC = Result;
5329     TC.setCorrectionRange(SS, TypoName);
5330     checkCorrectionVisibility(*this, TC);
5331     return TC;
5332   } else if (SecondBestTC && ObjCMessageReceiver) {
5333     // Prefer 'super' when we're completing in a message-receiver
5334     // context.
5335 
5336     if (BestTC.getCorrection().getAsString() != "super") {
5337       if (SecondBestTC.getCorrection().getAsString() == "super")
5338         BestTC = SecondBestTC;
5339       else if ((*Consumer)["super"].front().isKeyword())
5340         BestTC = (*Consumer)["super"].front();
5341     }
5342     // Don't correct to a keyword that's the same as the typo; the keyword
5343     // wasn't actually in scope.
5344     if (BestTC.getEditDistance() == 0 ||
5345         BestTC.getCorrection().getAsString() != "super")
5346       return FailedCorrection(Typo, TypoName.getLoc(), RecordFailure);
5347 
5348     BestTC.setCorrectionRange(SS, TypoName);
5349     return BestTC;
5350   }
5351 
5352   // Record the failure's location if needed and return an empty correction. If
5353   // this was an unqualified lookup and we believe the callback object did not
5354   // filter out possible corrections, also cache the failure for the typo.
5355   return FailedCorrection(Typo, TypoName.getLoc(), RecordFailure && !SecondBestTC);
5356 }
5357 
5358 TypoExpr *Sema::CorrectTypoDelayed(
5359     const DeclarationNameInfo &TypoName, Sema::LookupNameKind LookupKind,
5360     Scope *S, CXXScopeSpec *SS, CorrectionCandidateCallback &CCC,
5361     TypoDiagnosticGenerator TDG, TypoRecoveryCallback TRC, CorrectTypoKind Mode,
5362     DeclContext *MemberContext, bool EnteringContext,
5363     const ObjCObjectPointerType *OPT) {
5364   auto Consumer = makeTypoCorrectionConsumer(TypoName, LookupKind, S, SS, CCC,
5365                                              MemberContext, EnteringContext,
5366                                              OPT, Mode == CTK_ErrorRecovery);
5367 
5368   // Give the external sema source a chance to correct the typo.
5369   TypoCorrection ExternalTypo;
5370   if (ExternalSource && Consumer) {
5371     ExternalTypo = ExternalSource->CorrectTypo(
5372         TypoName, LookupKind, S, SS, *Consumer->getCorrectionValidator(),
5373         MemberContext, EnteringContext, OPT);
5374     if (ExternalTypo)
5375       Consumer->addCorrection(ExternalTypo);
5376   }
5377 
5378   if (!Consumer || Consumer->empty())
5379     return nullptr;
5380 
5381   // Make sure the best edit distance (prior to adding any namespace qualifiers)
5382   // is not more that about a third of the length of the typo's identifier.
5383   unsigned ED = Consumer->getBestEditDistance(true);
5384   IdentifierInfo *Typo = TypoName.getName().getAsIdentifierInfo();
5385   if (!ExternalTypo && ED > 0 && Typo->getName().size() / ED < 3)
5386     return nullptr;
5387   ExprEvalContexts.back().NumTypos++;
5388   return createDelayedTypo(std::move(Consumer), std::move(TDG), std::move(TRC),
5389                            TypoName.getLoc());
5390 }
5391 
5392 void TypoCorrection::addCorrectionDecl(NamedDecl *CDecl) {
5393   if (!CDecl) return;
5394 
5395   if (isKeyword())
5396     CorrectionDecls.clear();
5397 
5398   CorrectionDecls.push_back(CDecl);
5399 
5400   if (!CorrectionName)
5401     CorrectionName = CDecl->getDeclName();
5402 }
5403 
5404 std::string TypoCorrection::getAsString(const LangOptions &LO) const {
5405   if (CorrectionNameSpec) {
5406     std::string tmpBuffer;
5407     llvm::raw_string_ostream PrefixOStream(tmpBuffer);
5408     CorrectionNameSpec->print(PrefixOStream, PrintingPolicy(LO));
5409     PrefixOStream << CorrectionName;
5410     return PrefixOStream.str();
5411   }
5412 
5413   return CorrectionName.getAsString();
5414 }
5415 
5416 bool CorrectionCandidateCallback::ValidateCandidate(
5417     const TypoCorrection &candidate) {
5418   if (!candidate.isResolved())
5419     return true;
5420 
5421   if (candidate.isKeyword())
5422     return WantTypeSpecifiers || WantExpressionKeywords || WantCXXNamedCasts ||
5423            WantRemainingKeywords || WantObjCSuper;
5424 
5425   bool HasNonType = false;
5426   bool HasStaticMethod = false;
5427   bool HasNonStaticMethod = false;
5428   for (Decl *D : candidate) {
5429     if (FunctionTemplateDecl *FTD = dyn_cast<FunctionTemplateDecl>(D))
5430       D = FTD->getTemplatedDecl();
5431     if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(D)) {
5432       if (Method->isStatic())
5433         HasStaticMethod = true;
5434       else
5435         HasNonStaticMethod = true;
5436     }
5437     if (!isa<TypeDecl>(D))
5438       HasNonType = true;
5439   }
5440 
5441   if (IsAddressOfOperand && HasNonStaticMethod && !HasStaticMethod &&
5442       !candidate.getCorrectionSpecifier())
5443     return false;
5444 
5445   return WantTypeSpecifiers || HasNonType;
5446 }
5447 
5448 FunctionCallFilterCCC::FunctionCallFilterCCC(Sema &SemaRef, unsigned NumArgs,
5449                                              bool HasExplicitTemplateArgs,
5450                                              MemberExpr *ME)
5451     : NumArgs(NumArgs), HasExplicitTemplateArgs(HasExplicitTemplateArgs),
5452       CurContext(SemaRef.CurContext), MemberFn(ME) {
5453   WantTypeSpecifiers = false;
5454   WantFunctionLikeCasts = SemaRef.getLangOpts().CPlusPlus &&
5455                           !HasExplicitTemplateArgs && NumArgs == 1;
5456   WantCXXNamedCasts = HasExplicitTemplateArgs && NumArgs == 1;
5457   WantRemainingKeywords = false;
5458 }
5459 
5460 bool FunctionCallFilterCCC::ValidateCandidate(const TypoCorrection &candidate) {
5461   if (!candidate.getCorrectionDecl())
5462     return candidate.isKeyword();
5463 
5464   for (auto *C : candidate) {
5465     FunctionDecl *FD = nullptr;
5466     NamedDecl *ND = C->getUnderlyingDecl();
5467     if (FunctionTemplateDecl *FTD = dyn_cast<FunctionTemplateDecl>(ND))
5468       FD = FTD->getTemplatedDecl();
5469     if (!HasExplicitTemplateArgs && !FD) {
5470       if (!(FD = dyn_cast<FunctionDecl>(ND)) && isa<ValueDecl>(ND)) {
5471         // If the Decl is neither a function nor a template function,
5472         // determine if it is a pointer or reference to a function. If so,
5473         // check against the number of arguments expected for the pointee.
5474         QualType ValType = cast<ValueDecl>(ND)->getType();
5475         if (ValType.isNull())
5476           continue;
5477         if (ValType->isAnyPointerType() || ValType->isReferenceType())
5478           ValType = ValType->getPointeeType();
5479         if (const FunctionProtoType *FPT = ValType->getAs<FunctionProtoType>())
5480           if (FPT->getNumParams() == NumArgs)
5481             return true;
5482       }
5483     }
5484 
5485     // A typo for a function-style cast can look like a function call in C++.
5486     if ((HasExplicitTemplateArgs ? getAsTypeTemplateDecl(ND) != nullptr
5487                                  : isa<TypeDecl>(ND)) &&
5488         CurContext->getParentASTContext().getLangOpts().CPlusPlus)
5489       // Only a class or class template can take two or more arguments.
5490       return NumArgs <= 1 || HasExplicitTemplateArgs || isa<CXXRecordDecl>(ND);
5491 
5492     // Skip the current candidate if it is not a FunctionDecl or does not accept
5493     // the current number of arguments.
5494     if (!FD || !(FD->getNumParams() >= NumArgs &&
5495                  FD->getMinRequiredArguments() <= NumArgs))
5496       continue;
5497 
5498     // If the current candidate is a non-static C++ method, skip the candidate
5499     // unless the method being corrected--or the current DeclContext, if the
5500     // function being corrected is not a method--is a method in the same class
5501     // or a descendent class of the candidate's parent class.
5502     if (const auto *MD = dyn_cast<CXXMethodDecl>(FD)) {
5503       if (MemberFn || !MD->isStatic()) {
5504         const auto *CurMD =
5505             MemberFn
5506                 ? dyn_cast_if_present<CXXMethodDecl>(MemberFn->getMemberDecl())
5507                 : dyn_cast_if_present<CXXMethodDecl>(CurContext);
5508         const CXXRecordDecl *CurRD =
5509             CurMD ? CurMD->getParent()->getCanonicalDecl() : nullptr;
5510         const CXXRecordDecl *RD = MD->getParent()->getCanonicalDecl();
5511         if (!CurRD || (CurRD != RD && !CurRD->isDerivedFrom(RD)))
5512           continue;
5513       }
5514     }
5515     return true;
5516   }
5517   return false;
5518 }
5519 
5520 void Sema::diagnoseTypo(const TypoCorrection &Correction,
5521                         const PartialDiagnostic &TypoDiag,
5522                         bool ErrorRecovery) {
5523   diagnoseTypo(Correction, TypoDiag, PDiag(diag::note_previous_decl),
5524                ErrorRecovery);
5525 }
5526 
5527 /// Find which declaration we should import to provide the definition of
5528 /// the given declaration.
5529 static const NamedDecl *getDefinitionToImport(const NamedDecl *D) {
5530   if (const auto *VD = dyn_cast<VarDecl>(D))
5531     return VD->getDefinition();
5532   if (const auto *FD = dyn_cast<FunctionDecl>(D))
5533     return FD->getDefinition();
5534   if (const auto *TD = dyn_cast<TagDecl>(D))
5535     return TD->getDefinition();
5536   if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(D))
5537     return ID->getDefinition();
5538   if (const auto *PD = dyn_cast<ObjCProtocolDecl>(D))
5539     return PD->getDefinition();
5540   if (const auto *TD = dyn_cast<TemplateDecl>(D))
5541     if (const NamedDecl *TTD = TD->getTemplatedDecl())
5542       return getDefinitionToImport(TTD);
5543   return nullptr;
5544 }
5545 
5546 void Sema::diagnoseMissingImport(SourceLocation Loc, const NamedDecl *Decl,
5547                                  MissingImportKind MIK, bool Recover) {
5548   // Suggest importing a module providing the definition of this entity, if
5549   // possible.
5550   const NamedDecl *Def = getDefinitionToImport(Decl);
5551   if (!Def)
5552     Def = Decl;
5553 
5554   Module *Owner = getOwningModule(Def);
5555   assert(Owner && "definition of hidden declaration is not in a module");
5556 
5557   llvm::SmallVector<Module*, 8> OwningModules;
5558   OwningModules.push_back(Owner);
5559   auto Merged = Context.getModulesWithMergedDefinition(Def);
5560   OwningModules.insert(OwningModules.end(), Merged.begin(), Merged.end());
5561 
5562   diagnoseMissingImport(Loc, Def, Def->getLocation(), OwningModules, MIK,
5563                         Recover);
5564 }
5565 
5566 /// Get a "quoted.h" or <angled.h> include path to use in a diagnostic
5567 /// suggesting the addition of a #include of the specified file.
5568 static std::string getHeaderNameForHeader(Preprocessor &PP, FileEntryRef E,
5569                                           llvm::StringRef IncludingFile) {
5570   bool IsAngled = false;
5571   auto Path = PP.getHeaderSearchInfo().suggestPathToFileForDiagnostics(
5572       E, IncludingFile, &IsAngled);
5573   return (IsAngled ? '<' : '"') + Path + (IsAngled ? '>' : '"');
5574 }
5575 
5576 void Sema::diagnoseMissingImport(SourceLocation UseLoc, const NamedDecl *Decl,
5577                                  SourceLocation DeclLoc,
5578                                  ArrayRef<Module *> Modules,
5579                                  MissingImportKind MIK, bool Recover) {
5580   assert(!Modules.empty());
5581 
5582   // See https://github.com/llvm/llvm-project/issues/73893. It is generally
5583   // confusing than helpful to show the namespace is not visible.
5584   if (isa<NamespaceDecl>(Decl))
5585     return;
5586 
5587   auto NotePrevious = [&] {
5588     // FIXME: Suppress the note backtrace even under
5589     // -fdiagnostics-show-note-include-stack. We don't care how this
5590     // declaration was previously reached.
5591     Diag(DeclLoc, diag::note_unreachable_entity) << (int)MIK;
5592   };
5593 
5594   // Weed out duplicates from module list.
5595   llvm::SmallVector<Module*, 8> UniqueModules;
5596   llvm::SmallDenseSet<Module*, 8> UniqueModuleSet;
5597   for (auto *M : Modules) {
5598     if (M->isExplicitGlobalModule() || M->isPrivateModule())
5599       continue;
5600     if (UniqueModuleSet.insert(M).second)
5601       UniqueModules.push_back(M);
5602   }
5603 
5604   // Try to find a suitable header-name to #include.
5605   std::string HeaderName;
5606   if (OptionalFileEntryRef Header =
5607           PP.getHeaderToIncludeForDiagnostics(UseLoc, DeclLoc)) {
5608     if (const FileEntry *FE =
5609             SourceMgr.getFileEntryForID(SourceMgr.getFileID(UseLoc)))
5610       HeaderName =
5611           getHeaderNameForHeader(PP, *Header, FE->tryGetRealPathName());
5612   }
5613 
5614   // If we have a #include we should suggest, or if all definition locations
5615   // were in global module fragments, don't suggest an import.
5616   if (!HeaderName.empty() || UniqueModules.empty()) {
5617     // FIXME: Find a smart place to suggest inserting a #include, and add
5618     // a FixItHint there.
5619     Diag(UseLoc, diag::err_module_unimported_use_header)
5620         << (int)MIK << Decl << !HeaderName.empty() << HeaderName;
5621     // Produce a note showing where the entity was declared.
5622     NotePrevious();
5623     if (Recover)
5624       createImplicitModuleImportForErrorRecovery(UseLoc, Modules[0]);
5625     return;
5626   }
5627 
5628   Modules = UniqueModules;
5629 
5630   auto GetModuleNameForDiagnostic = [this](const Module *M) -> std::string {
5631     if (M->isModuleMapModule())
5632       return M->getFullModuleName();
5633 
5634     if (M->isImplicitGlobalModule())
5635       M = M->getTopLevelModule();
5636 
5637     // If the current module unit is in the same module with M, it is OK to show
5638     // the partition name. Otherwise, it'll be sufficient to show the primary
5639     // module name.
5640     if (getASTContext().isInSameModule(M, getCurrentModule()))
5641       return M->getTopLevelModuleName().str();
5642     else
5643       return M->getPrimaryModuleInterfaceName().str();
5644   };
5645 
5646   if (Modules.size() > 1) {
5647     std::string ModuleList;
5648     unsigned N = 0;
5649     for (const auto *M : Modules) {
5650       ModuleList += "\n        ";
5651       if (++N == 5 && N != Modules.size()) {
5652         ModuleList += "[...]";
5653         break;
5654       }
5655       ModuleList += GetModuleNameForDiagnostic(M);
5656     }
5657 
5658     Diag(UseLoc, diag::err_module_unimported_use_multiple)
5659       << (int)MIK << Decl << ModuleList;
5660   } else {
5661     // FIXME: Add a FixItHint that imports the corresponding module.
5662     Diag(UseLoc, diag::err_module_unimported_use)
5663         << (int)MIK << Decl << GetModuleNameForDiagnostic(Modules[0]);
5664   }
5665 
5666   NotePrevious();
5667 
5668   // Try to recover by implicitly importing this module.
5669   if (Recover)
5670     createImplicitModuleImportForErrorRecovery(UseLoc, Modules[0]);
5671 }
5672 
5673 void Sema::diagnoseTypo(const TypoCorrection &Correction,
5674                         const PartialDiagnostic &TypoDiag,
5675                         const PartialDiagnostic &PrevNote,
5676                         bool ErrorRecovery) {
5677   std::string CorrectedStr = Correction.getAsString(getLangOpts());
5678   std::string CorrectedQuotedStr = Correction.getQuoted(getLangOpts());
5679   FixItHint FixTypo = FixItHint::CreateReplacement(
5680       Correction.getCorrectionRange(), CorrectedStr);
5681 
5682   // Maybe we're just missing a module import.
5683   if (Correction.requiresImport()) {
5684     NamedDecl *Decl = Correction.getFoundDecl();
5685     assert(Decl && "import required but no declaration to import");
5686 
5687     diagnoseMissingImport(Correction.getCorrectionRange().getBegin(), Decl,
5688                           MissingImportKind::Declaration, ErrorRecovery);
5689     return;
5690   }
5691 
5692   Diag(Correction.getCorrectionRange().getBegin(), TypoDiag)
5693     << CorrectedQuotedStr << (ErrorRecovery ? FixTypo : FixItHint());
5694 
5695   NamedDecl *ChosenDecl =
5696       Correction.isKeyword() ? nullptr : Correction.getFoundDecl();
5697 
5698   // For builtin functions which aren't declared anywhere in source,
5699   // don't emit the "declared here" note.
5700   if (const auto *FD = dyn_cast_if_present<FunctionDecl>(ChosenDecl);
5701       FD && FD->getBuiltinID() &&
5702       PrevNote.getDiagID() == diag::note_previous_decl &&
5703       Correction.getCorrectionRange().getBegin() == FD->getBeginLoc()) {
5704     ChosenDecl = nullptr;
5705   }
5706 
5707   if (PrevNote.getDiagID() && ChosenDecl)
5708     Diag(ChosenDecl->getLocation(), PrevNote)
5709       << CorrectedQuotedStr << (ErrorRecovery ? FixItHint() : FixTypo);
5710 
5711   // Add any extra diagnostics.
5712   for (const PartialDiagnostic &PD : Correction.getExtraDiagnostics())
5713     Diag(Correction.getCorrectionRange().getBegin(), PD);
5714 }
5715 
5716 TypoExpr *Sema::createDelayedTypo(std::unique_ptr<TypoCorrectionConsumer> TCC,
5717                                   TypoDiagnosticGenerator TDG,
5718                                   TypoRecoveryCallback TRC,
5719                                   SourceLocation TypoLoc) {
5720   assert(TCC && "createDelayedTypo requires a valid TypoCorrectionConsumer");
5721   auto TE = new (Context) TypoExpr(Context.DependentTy, TypoLoc);
5722   auto &State = DelayedTypos[TE];
5723   State.Consumer = std::move(TCC);
5724   State.DiagHandler = std::move(TDG);
5725   State.RecoveryHandler = std::move(TRC);
5726   if (TE)
5727     TypoExprs.push_back(TE);
5728   return TE;
5729 }
5730 
5731 const Sema::TypoExprState &Sema::getTypoExprState(TypoExpr *TE) const {
5732   auto Entry = DelayedTypos.find(TE);
5733   assert(Entry != DelayedTypos.end() &&
5734          "Failed to get the state for a TypoExpr!");
5735   return Entry->second;
5736 }
5737 
5738 void Sema::clearDelayedTypo(TypoExpr *TE) {
5739   DelayedTypos.erase(TE);
5740 }
5741 
5742 void Sema::ActOnPragmaDump(Scope *S, SourceLocation IILoc, IdentifierInfo *II) {
5743   DeclarationNameInfo Name(II, IILoc);
5744   LookupResult R(*this, Name, LookupAnyName,
5745                  RedeclarationKind::NotForRedeclaration);
5746   R.suppressDiagnostics();
5747   R.setHideTags(false);
5748   LookupName(R, S);
5749   R.dump();
5750 }
5751 
5752 void Sema::ActOnPragmaDump(Expr *E) {
5753   E->dump();
5754 }
5755 
5756 RedeclarationKind Sema::forRedeclarationInCurContext() const {
5757   // A declaration with an owning module for linkage can never link against
5758   // anything that is not visible. We don't need to check linkage here; if
5759   // the context has internal linkage, redeclaration lookup won't find things
5760   // from other TUs, and we can't safely compute linkage yet in general.
5761   if (cast<Decl>(CurContext)->getOwningModuleForLinkage())
5762     return RedeclarationKind::ForVisibleRedeclaration;
5763   return RedeclarationKind::ForExternalRedeclaration;
5764 }
5765