Lookup.h revision 447af24a003aa8d0dc7317a56f06f5b8361f8808
1//===--- Lookup.h - Classes for name lookup ---------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the LookupResult class, which is integral to 11// Sema's name-lookup subsystem. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_CLANG_SEMA_LOOKUP_H 16#define LLVM_CLANG_SEMA_LOOKUP_H 17 18#include "clang/Sema/Sema.h" 19#include "clang/AST/DeclCXX.h" 20 21namespace clang { 22 23/// @brief Represents the results of name lookup. 24/// 25/// An instance of the LookupResult class captures the results of a 26/// single name lookup, which can return no result (nothing found), 27/// a single declaration, a set of overloaded functions, or an 28/// ambiguity. Use the getKind() method to determine which of these 29/// results occurred for a given lookup. 30class LookupResult { 31public: 32 enum LookupResultKind { 33 /// @brief No entity found met the criteria. 34 NotFound = 0, 35 36 /// @brief No entity found met the criteria within the current 37 /// instantiation,, but there were dependent base classes of the 38 /// current instantiation that could not be searched. 39 NotFoundInCurrentInstantiation, 40 41 /// @brief Name lookup found a single declaration that met the 42 /// criteria. getFoundDecl() will return this declaration. 43 Found, 44 45 /// @brief Name lookup found a set of overloaded functions that 46 /// met the criteria. 47 FoundOverloaded, 48 49 /// @brief Name lookup found an unresolvable value declaration 50 /// and cannot yet complete. This only happens in C++ dependent 51 /// contexts with dependent using declarations. 52 FoundUnresolvedValue, 53 54 /// @brief Name lookup results in an ambiguity; use 55 /// getAmbiguityKind to figure out what kind of ambiguity 56 /// we have. 57 Ambiguous 58 }; 59 60 enum AmbiguityKind { 61 /// Name lookup results in an ambiguity because multiple 62 /// entities that meet the lookup criteria were found in 63 /// subobjects of different types. For example: 64 /// @code 65 /// struct A { void f(int); } 66 /// struct B { void f(double); } 67 /// struct C : A, B { }; 68 /// void test(C c) { 69 /// c.f(0); // error: A::f and B::f come from subobjects of different 70 /// // types. overload resolution is not performed. 71 /// } 72 /// @endcode 73 AmbiguousBaseSubobjectTypes, 74 75 /// Name lookup results in an ambiguity because multiple 76 /// nonstatic entities that meet the lookup criteria were found 77 /// in different subobjects of the same type. For example: 78 /// @code 79 /// struct A { int x; }; 80 /// struct B : A { }; 81 /// struct C : A { }; 82 /// struct D : B, C { }; 83 /// int test(D d) { 84 /// return d.x; // error: 'x' is found in two A subobjects (of B and C) 85 /// } 86 /// @endcode 87 AmbiguousBaseSubobjects, 88 89 /// Name lookup results in an ambiguity because multiple definitions 90 /// of entity that meet the lookup criteria were found in different 91 /// declaration contexts. 92 /// @code 93 /// namespace A { 94 /// int i; 95 /// namespace B { int i; } 96 /// int test() { 97 /// using namespace B; 98 /// return i; // error 'i' is found in namespace A and A::B 99 /// } 100 /// } 101 /// @endcode 102 AmbiguousReference, 103 104 /// Name lookup results in an ambiguity because an entity with a 105 /// tag name was hidden by an entity with an ordinary name from 106 /// a different context. 107 /// @code 108 /// namespace A { struct Foo {}; } 109 /// namespace B { void Foo(); } 110 /// namespace C { 111 /// using namespace A; 112 /// using namespace B; 113 /// } 114 /// void test() { 115 /// C::Foo(); // error: tag 'A::Foo' is hidden by an object in a 116 /// // different namespace 117 /// } 118 /// @endcode 119 AmbiguousTagHiding 120 }; 121 122 /// A little identifier for flagging temporary lookup results. 123 enum TemporaryToken { 124 Temporary 125 }; 126 127 typedef UnresolvedSetImpl::iterator iterator; 128 129 LookupResult(Sema &SemaRef, const DeclarationNameInfo &NameInfo, 130 Sema::LookupNameKind LookupKind, 131 Sema::RedeclarationKind Redecl = Sema::NotForRedeclaration) 132 : ResultKind(NotFound), 133 Paths(0), 134 NamingClass(0), 135 SemaRef(SemaRef), 136 NameInfo(NameInfo), 137 LookupKind(LookupKind), 138 IDNS(0), 139 Redecl(Redecl != Sema::NotForRedeclaration), 140 HideTags(true), 141 Diagnose(Redecl == Sema::NotForRedeclaration) 142 { 143 configure(); 144 } 145 146 // TODO: consider whether this constructor should be restricted to take 147 // as input a const IndentifierInfo* (instead of Name), 148 // forcing other cases towards the constructor taking a DNInfo. 149 LookupResult(Sema &SemaRef, DeclarationName Name, 150 SourceLocation NameLoc, Sema::LookupNameKind LookupKind, 151 Sema::RedeclarationKind Redecl = Sema::NotForRedeclaration) 152 : ResultKind(NotFound), 153 Paths(0), 154 NamingClass(0), 155 SemaRef(SemaRef), 156 NameInfo(Name, NameLoc), 157 LookupKind(LookupKind), 158 IDNS(0), 159 Redecl(Redecl != Sema::NotForRedeclaration), 160 HideTags(true), 161 Diagnose(Redecl == Sema::NotForRedeclaration) 162 { 163 configure(); 164 } 165 166 /// Creates a temporary lookup result, initializing its core data 167 /// using the information from another result. Diagnostics are always 168 /// disabled. 169 LookupResult(TemporaryToken _, const LookupResult &Other) 170 : ResultKind(NotFound), 171 Paths(0), 172 NamingClass(0), 173 SemaRef(Other.SemaRef), 174 NameInfo(Other.NameInfo), 175 LookupKind(Other.LookupKind), 176 IDNS(Other.IDNS), 177 Redecl(Other.Redecl), 178 HideTags(Other.HideTags), 179 Diagnose(false) 180 {} 181 182 ~LookupResult() { 183 if (Diagnose) diagnose(); 184 if (Paths) deletePaths(Paths); 185 } 186 187 /// Gets the name info to look up. 188 const DeclarationNameInfo &getLookupNameInfo() const { 189 return NameInfo; 190 } 191 192 /// \brief Sets the name info to look up. 193 void setLookupNameInfo(const DeclarationNameInfo &NameInfo) { 194 this->NameInfo = NameInfo; 195 } 196 197 /// Gets the name to look up. 198 DeclarationName getLookupName() const { 199 return NameInfo.getName(); 200 } 201 202 /// \brief Sets the name to look up. 203 void setLookupName(DeclarationName Name) { 204 NameInfo.setName(Name); 205 } 206 207 /// Gets the kind of lookup to perform. 208 Sema::LookupNameKind getLookupKind() const { 209 return LookupKind; 210 } 211 212 /// True if this lookup is just looking for an existing declaration. 213 bool isForRedeclaration() const { 214 return Redecl; 215 } 216 217 /// \brief Determine whether this lookup is permitted to see hidden 218 /// declarations, such as those in modules that have not yet been imported. 219 bool isHiddenDeclarationVisible() const { 220 return Redecl || LookupKind == Sema::LookupTagName; 221 } 222 223 /// Sets whether tag declarations should be hidden by non-tag 224 /// declarations during resolution. The default is true. 225 void setHideTags(bool Hide) { 226 HideTags = Hide; 227 } 228 229 bool isAmbiguous() const { 230 return getResultKind() == Ambiguous; 231 } 232 233 /// Determines if this names a single result which is not an 234 /// unresolved value using decl. If so, it is safe to call 235 /// getFoundDecl(). 236 bool isSingleResult() const { 237 return getResultKind() == Found; 238 } 239 240 /// Determines if the results are overloaded. 241 bool isOverloadedResult() const { 242 return getResultKind() == FoundOverloaded; 243 } 244 245 bool isUnresolvableResult() const { 246 return getResultKind() == FoundUnresolvedValue; 247 } 248 249 LookupResultKind getResultKind() const { 250 sanity(); 251 return ResultKind; 252 } 253 254 AmbiguityKind getAmbiguityKind() const { 255 assert(isAmbiguous()); 256 return Ambiguity; 257 } 258 259 const UnresolvedSetImpl &asUnresolvedSet() const { 260 return Decls; 261 } 262 263 iterator begin() const { return iterator(Decls.begin()); } 264 iterator end() const { return iterator(Decls.end()); } 265 266 /// \brief Return true if no decls were found 267 bool empty() const { return Decls.empty(); } 268 269 /// \brief Return the base paths structure that's associated with 270 /// these results, or null if none is. 271 CXXBasePaths *getBasePaths() const { 272 return Paths; 273 } 274 275 /// \brief Determine whether the given declaration is visible to the 276 /// program. 277 static bool isVisible(NamedDecl *D) { 278 // So long as this declaration is not module-private or was parsed as 279 // part of this translation unit (i.e., in the module), it's visible. 280 if (!D->isModulePrivate() || !D->isFromASTFile()) 281 return true; 282 283 // FIXME: We should be allowed to refer to a module-private name from 284 // within the same module, e.g., during template instantiation. 285 // This requires us know which module a particular declaration came from. 286 return false; 287 } 288 289 /// \brief Retrieve the accepted (re)declaration of the given declaration, 290 /// if there is one. 291 NamedDecl *getAcceptableDecl(NamedDecl *D) const { 292 if (!D->isInIdentifierNamespace(IDNS)) 293 return 0; 294 295 if (isHiddenDeclarationVisible() || isVisible(D)) 296 return D; 297 298 return getAcceptableDeclSlow(D); 299 } 300 301private: 302 NamedDecl *getAcceptableDeclSlow(NamedDecl *D) const; 303public: 304 305 /// \brief Returns the identifier namespace mask for this lookup. 306 unsigned getIdentifierNamespace() const { 307 return IDNS; 308 } 309 310 /// \brief Returns whether these results arose from performing a 311 /// lookup into a class. 312 bool isClassLookup() const { 313 return NamingClass != 0; 314 } 315 316 /// \brief Returns the 'naming class' for this lookup, i.e. the 317 /// class which was looked into to find these results. 318 /// 319 /// C++0x [class.access.base]p5: 320 /// The access to a member is affected by the class in which the 321 /// member is named. This naming class is the class in which the 322 /// member name was looked up and found. [Note: this class can be 323 /// explicit, e.g., when a qualified-id is used, or implicit, 324 /// e.g., when a class member access operator (5.2.5) is used 325 /// (including cases where an implicit "this->" is added). If both 326 /// a class member access operator and a qualified-id are used to 327 /// name the member (as in p->T::m), the class naming the member 328 /// is the class named by the nested-name-specifier of the 329 /// qualified-id (that is, T). -- end note ] 330 /// 331 /// This is set by the lookup routines when they find results in a class. 332 CXXRecordDecl *getNamingClass() const { 333 return NamingClass; 334 } 335 336 /// \brief Sets the 'naming class' for this lookup. 337 void setNamingClass(CXXRecordDecl *Record) { 338 NamingClass = Record; 339 } 340 341 /// \brief Returns the base object type associated with this lookup; 342 /// important for [class.protected]. Most lookups do not have an 343 /// associated base object. 344 QualType getBaseObjectType() const { 345 return BaseObjectType; 346 } 347 348 /// \brief Sets the base object type for this lookup. 349 void setBaseObjectType(QualType T) { 350 BaseObjectType = T; 351 } 352 353 /// \brief Add a declaration to these results with its natural access. 354 /// Does not test the acceptance criteria. 355 void addDecl(NamedDecl *D) { 356 addDecl(D, D->getAccess()); 357 } 358 359 /// \brief Add a declaration to these results with the given access. 360 /// Does not test the acceptance criteria. 361 void addDecl(NamedDecl *D, AccessSpecifier AS) { 362 Decls.addDecl(D, AS); 363 ResultKind = Found; 364 } 365 366 /// \brief Add all the declarations from another set of lookup 367 /// results. 368 void addAllDecls(const LookupResult &Other) { 369 Decls.append(Other.Decls.begin(), Other.Decls.end()); 370 ResultKind = Found; 371 } 372 373 /// \brief Determine whether no result was found because we could not 374 /// search into dependent base classes of the current instantiation. 375 bool wasNotFoundInCurrentInstantiation() const { 376 return ResultKind == NotFoundInCurrentInstantiation; 377 } 378 379 /// \brief Note that while no result was found in the current instantiation, 380 /// there were dependent base classes that could not be searched. 381 void setNotFoundInCurrentInstantiation() { 382 assert(ResultKind == NotFound && Decls.empty()); 383 ResultKind = NotFoundInCurrentInstantiation; 384 } 385 386 /// \brief Resolves the result kind of the lookup, possibly hiding 387 /// decls. 388 /// 389 /// This should be called in any environment where lookup might 390 /// generate multiple lookup results. 391 void resolveKind(); 392 393 /// \brief Re-resolves the result kind of the lookup after a set of 394 /// removals has been performed. 395 void resolveKindAfterFilter() { 396 if (Decls.empty()) { 397 if (ResultKind != NotFoundInCurrentInstantiation) 398 ResultKind = NotFound; 399 400 if (Paths) { 401 deletePaths(Paths); 402 Paths = 0; 403 } 404 } else { 405 AmbiguityKind SavedAK = Ambiguity; 406 ResultKind = Found; 407 resolveKind(); 408 409 // If we didn't make the lookup unambiguous, restore the old 410 // ambiguity kind. 411 if (ResultKind == Ambiguous) { 412 Ambiguity = SavedAK; 413 } else if (Paths) { 414 deletePaths(Paths); 415 Paths = 0; 416 } 417 } 418 } 419 420 template <class DeclClass> 421 DeclClass *getAsSingle() const { 422 if (getResultKind() != Found) return 0; 423 return dyn_cast<DeclClass>(getFoundDecl()); 424 } 425 426 /// \brief Fetch the unique decl found by this lookup. Asserts 427 /// that one was found. 428 /// 429 /// This is intended for users who have examined the result kind 430 /// and are certain that there is only one result. 431 NamedDecl *getFoundDecl() const { 432 assert(getResultKind() == Found 433 && "getFoundDecl called on non-unique result"); 434 return (*begin())->getUnderlyingDecl(); 435 } 436 437 /// Fetches a representative decl. Useful for lazy diagnostics. 438 NamedDecl *getRepresentativeDecl() const { 439 assert(!Decls.empty() && "cannot get representative of empty set"); 440 return *begin(); 441 } 442 443 /// \brief Asks if the result is a single tag decl. 444 bool isSingleTagDecl() const { 445 return getResultKind() == Found && isa<TagDecl>(getFoundDecl()); 446 } 447 448 /// \brief Make these results show that the name was found in 449 /// base classes of different types. 450 /// 451 /// The given paths object is copied and invalidated. 452 void setAmbiguousBaseSubobjectTypes(CXXBasePaths &P); 453 454 /// \brief Make these results show that the name was found in 455 /// distinct base classes of the same type. 456 /// 457 /// The given paths object is copied and invalidated. 458 void setAmbiguousBaseSubobjects(CXXBasePaths &P); 459 460 /// \brief Make these results show that the name was found in 461 /// different contexts and a tag decl was hidden by an ordinary 462 /// decl in a different context. 463 void setAmbiguousQualifiedTagHiding() { 464 setAmbiguous(AmbiguousTagHiding); 465 } 466 467 /// \brief Clears out any current state. 468 void clear() { 469 ResultKind = NotFound; 470 Decls.clear(); 471 if (Paths) deletePaths(Paths); 472 Paths = NULL; 473 NamingClass = 0; 474 } 475 476 /// \brief Clears out any current state and re-initializes for a 477 /// different kind of lookup. 478 void clear(Sema::LookupNameKind Kind) { 479 clear(); 480 LookupKind = Kind; 481 configure(); 482 } 483 484 /// \brief Change this lookup's redeclaration kind. 485 void setRedeclarationKind(Sema::RedeclarationKind RK) { 486 Redecl = RK; 487 configure(); 488 } 489 490 void print(raw_ostream &); 491 492 /// Suppress the diagnostics that would normally fire because of this 493 /// lookup. This happens during (e.g.) redeclaration lookups. 494 void suppressDiagnostics() { 495 Diagnose = false; 496 } 497 498 /// Determines whether this lookup is suppressing diagnostics. 499 bool isSuppressingDiagnostics() const { 500 return !Diagnose; 501 } 502 503 /// Sets a 'context' source range. 504 void setContextRange(SourceRange SR) { 505 NameContextRange = SR; 506 } 507 508 /// Gets the source range of the context of this name; for C++ 509 /// qualified lookups, this is the source range of the scope 510 /// specifier. 511 SourceRange getContextRange() const { 512 return NameContextRange; 513 } 514 515 /// Gets the location of the identifier. This isn't always defined: 516 /// sometimes we're doing lookups on synthesized names. 517 SourceLocation getNameLoc() const { 518 return NameInfo.getLoc(); 519 } 520 521 /// \brief Get the Sema object that this lookup result is searching 522 /// with. 523 Sema &getSema() const { return SemaRef; } 524 525 /// A class for iterating through a result set and possibly 526 /// filtering out results. The results returned are possibly 527 /// sugared. 528 class Filter { 529 LookupResult &Results; 530 LookupResult::iterator I; 531 bool Changed; 532 bool CalledDone; 533 534 friend class LookupResult; 535 Filter(LookupResult &Results) 536 : Results(Results), I(Results.begin()), Changed(false), CalledDone(false) 537 {} 538 539 public: 540 ~Filter() { 541 assert(CalledDone && 542 "LookupResult::Filter destroyed without done() call"); 543 } 544 545 bool hasNext() const { 546 return I != Results.end(); 547 } 548 549 NamedDecl *next() { 550 assert(I != Results.end() && "next() called on empty filter"); 551 return *I++; 552 } 553 554 /// Erase the last element returned from this iterator. 555 void erase() { 556 Results.Decls.erase(--I); 557 Changed = true; 558 } 559 560 /// Replaces the current entry with the given one, preserving the 561 /// access bits. 562 void replace(NamedDecl *D) { 563 Results.Decls.replace(I-1, D); 564 Changed = true; 565 } 566 567 /// Replaces the current entry with the given one. 568 void replace(NamedDecl *D, AccessSpecifier AS) { 569 Results.Decls.replace(I-1, D, AS); 570 Changed = true; 571 } 572 573 void done() { 574 assert(!CalledDone && "done() called twice"); 575 CalledDone = true; 576 577 if (Changed) 578 Results.resolveKindAfterFilter(); 579 } 580 }; 581 582 /// Create a filter for this result set. 583 Filter makeFilter() { 584 return Filter(*this); 585 } 586 587private: 588 void diagnose() { 589 if (isAmbiguous()) 590 SemaRef.DiagnoseAmbiguousLookup(*this); 591 else if (isClassLookup() && SemaRef.getLangOptions().AccessControl) 592 SemaRef.CheckLookupAccess(*this); 593 } 594 595 void setAmbiguous(AmbiguityKind AK) { 596 ResultKind = Ambiguous; 597 Ambiguity = AK; 598 } 599 600 void addDeclsFromBasePaths(const CXXBasePaths &P); 601 void configure(); 602 603 // Sanity checks. 604 void sanity() const; 605 606 bool sanityCheckUnresolved() const { 607 for (iterator I = begin(), E = end(); I != E; ++I) 608 if (isa<UnresolvedUsingValueDecl>(*I)) 609 return true; 610 return false; 611 } 612 613 static void deletePaths(CXXBasePaths *); 614 615 // Results. 616 LookupResultKind ResultKind; 617 AmbiguityKind Ambiguity; // ill-defined unless ambiguous 618 UnresolvedSet<8> Decls; 619 CXXBasePaths *Paths; 620 CXXRecordDecl *NamingClass; 621 QualType BaseObjectType; 622 623 // Parameters. 624 Sema &SemaRef; 625 DeclarationNameInfo NameInfo; 626 SourceRange NameContextRange; 627 Sema::LookupNameKind LookupKind; 628 unsigned IDNS; // set by configure() 629 630 bool Redecl; 631 632 /// \brief True if tag declarations should be hidden if non-tags 633 /// are present 634 bool HideTags; 635 636 bool Diagnose; 637}; 638 639 /// \brief Consumes visible declarations found when searching for 640 /// all visible names within a given scope or context. 641 /// 642 /// This abstract class is meant to be subclassed by clients of \c 643 /// Sema::LookupVisibleDecls(), each of which should override the \c 644 /// FoundDecl() function to process declarations as they are found. 645 class VisibleDeclConsumer { 646 public: 647 /// \brief Destroys the visible declaration consumer. 648 virtual ~VisibleDeclConsumer(); 649 650 /// \brief Invoked each time \p Sema::LookupVisibleDecls() finds a 651 /// declaration visible from the current scope or context. 652 /// 653 /// \param ND the declaration found. 654 /// 655 /// \param Hiding a declaration that hides the declaration \p ND, 656 /// or NULL if no such declaration exists. 657 /// 658 /// \param Ctx the original context from which the lookup started. 659 /// 660 /// \param InBaseClass whether this declaration was found in base 661 /// class of the context we searched. 662 virtual void FoundDecl(NamedDecl *ND, NamedDecl *Hiding, DeclContext *Ctx, 663 bool InBaseClass) = 0; 664 }; 665 666/// \brief A class for storing results from argument-dependent lookup. 667class ADLResult { 668private: 669 /// A map from canonical decls to the 'most recent' decl. 670 llvm::DenseMap<NamedDecl*, NamedDecl*> Decls; 671 672public: 673 /// Adds a new ADL candidate to this map. 674 void insert(NamedDecl *D); 675 676 /// Removes any data associated with a given decl. 677 void erase(NamedDecl *D) { 678 Decls.erase(cast<NamedDecl>(D->getCanonicalDecl())); 679 } 680 681 class iterator { 682 typedef llvm::DenseMap<NamedDecl*,NamedDecl*>::iterator inner_iterator; 683 inner_iterator iter; 684 685 friend class ADLResult; 686 iterator(const inner_iterator &iter) : iter(iter) {} 687 public: 688 iterator() {} 689 690 iterator &operator++() { ++iter; return *this; } 691 iterator operator++(int) { return iterator(iter++); } 692 693 NamedDecl *operator*() const { return iter->second; } 694 695 bool operator==(const iterator &other) const { return iter == other.iter; } 696 bool operator!=(const iterator &other) const { return iter != other.iter; } 697 }; 698 699 iterator begin() { return iterator(Decls.begin()); } 700 iterator end() { return iterator(Decls.end()); } 701}; 702 703} 704 705#endif 706