Sema.h

//===--- Sema.h - Semantic Analysis & AST Building --------------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the Sema class, which performs semantic analysis and
// builds ASTs.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_AST_SEMA_H
#define LLVM_CLANG_AST_SEMA_H

#include "IdentifierResolver.h"
#include "CXXFieldCollector.h"
#include "SemaOverload.h"
#include "clang/AST/DeclBase.h"
#include "clang/Parse/Action.h"
#include "clang/Sema/SemaDiagnostic.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/OwningPtr.h"
#include <string>
#include <vector>

namespace llvm {
  class APSInt;
}

namespace clang {
  class ASTContext;
  class ASTConsumer;
  class Preprocessor;
  class Decl;
  class DeclContext;
  class DeclSpec;
  class NamedDecl;
  class Stmt;
  class Expr;
  class InitListExpr;
  class DesignatedInitExpr;
  class CallExpr;
  class DeclRefExpr;
  class VarDecl;
  class ParmVarDecl;
  class TypedefDecl;
  class FunctionDecl;
  class QualType;
  struct LangOptions;
  class Token;
  class IntegerLiteral;
  class StringLiteral;
  class ArrayType;
  class LabelStmt;
  class SwitchStmt;
  class ExtVectorType;
  class TypedefDecl;
  class TemplateDecl;
  class TemplateArgument;
  class TemplateParameterList;
  class TemplateTemplateParmDecl;
  class ClassTemplateDecl;
  class ObjCInterfaceDecl;
  class ObjCCompatibleAliasDecl;
  class ObjCProtocolDecl;
  class ObjCImplementationDecl;
  class ObjCCategoryImplDecl;
  class ObjCCategoryDecl;
  class ObjCIvarDecl;
  class ObjCMethodDecl;
  class ObjCPropertyDecl;
  class ObjCContainerDecl;
  struct BlockSemaInfo;
  class BasePaths;
  class MemberLookupCriteria;

/// Sema - This implements semantic analysis and AST building for C.
class Sema : public Action {
  Sema(const Sema&);           // DO NOT IMPLEMENT
  void operator=(const Sema&); // DO NOT IMPLEMENT
public:
  const LangOptions &LangOpts;
  Preprocessor &PP;
  ASTContext &Context;
  ASTConsumer &Consumer;
  Diagnostic &Diags;
  SourceManager &SourceMgr;

  /// CurContext - This is the current declaration context of parsing.
  DeclContext *CurContext;

  /// PreDeclaratorDC - Keeps the declaration context before switching to the
  /// context of a declarator's nested-name-specifier.
  DeclContext *PreDeclaratorDC;

  /// CurBlock - If inside of a block definition, this contains a pointer to
  /// the active block object that represents it.
  BlockSemaInfo *CurBlock;

  /// PackContext - Manages the stack for #pragma pack. An alignment
  /// of 0 indicates default alignment.
  void *PackContext; // Really a "PragmaPackStack*"

  /// LabelMap - This is a mapping from label identifiers to the LabelStmt for
  /// it (which acts like the label decl in some ways).  Forward referenced
  /// labels have a LabelStmt created for them with a null location & SubStmt.
  llvm::DenseMap<IdentifierInfo*, LabelStmt*> LabelMap;
  
  llvm::SmallVector<SwitchStmt*, 8> SwitchStack;
  
  /// ExtVectorDecls - This is a list all the extended vector types. This allows
  /// us to associate a raw vector type with one of the ext_vector type names.
  /// This is only necessary for issuing pretty diagnostics.
  llvm::SmallVector<TypedefDecl*, 24> ExtVectorDecls;

  /// ObjCImplementations - Keep track of all class @implementations
  /// so we can emit errors on duplicates.
  llvm::DenseMap<IdentifierInfo*, ObjCImplementationDecl*> ObjCImplementations;
  
  /// ObjCCategoryImpls - Maintain a list of category implementations so 
  /// we can check for duplicates and find local method declarations.
  llvm::SmallVector<ObjCCategoryImplDecl*, 8> ObjCCategoryImpls;
  
  /// ObjCProtocols - Keep track of all protocol declarations declared
  /// with @protocol keyword, so that we can emit errors on duplicates and
  /// find the declarations when needed.
  llvm::DenseMap<IdentifierInfo*, ObjCProtocolDecl*> ObjCProtocols;

  /// ObjCInterfaceDecls - Keep track of all class declarations declared
  /// with @interface, so that we can emit errors on duplicates and
  /// find the declarations when needed. 
  typedef llvm::DenseMap<const IdentifierInfo*, 
                         ObjCInterfaceDecl*> ObjCInterfaceDeclsTy;
  ObjCInterfaceDeclsTy ObjCInterfaceDecls;
    
  /// ObjCAliasDecls - Keep track of all class declarations declared
  /// with @compatibility_alias, so that we can emit errors on duplicates and
  /// find the declarations when needed. This construct is ancient and will
  /// likely never be seen. Nevertheless, it is here for compatibility.
  typedef llvm::DenseMap<const IdentifierInfo*, 
                         ObjCCompatibleAliasDecl*> ObjCAliasTy;
  ObjCAliasTy ObjCAliasDecls;

  /// FieldCollector - Collects CXXFieldDecls during parsing of C++ classes.
  llvm::OwningPtr<CXXFieldCollector> FieldCollector;

  IdentifierResolver IdResolver;

  // Enum values used by KnownFunctionIDs (see below).
  enum {
    id_NSLog,
    id_NSLogv,
    id_asprintf,
    id_vasprintf,
    id_num_known_functions
  };
  
  /// KnownFunctionIDs - This is a list of IdentifierInfo objects to a set
  /// of known functions used by the semantic analysis to do various
  /// kinds of checking (e.g. checking format string errors in printf calls).
  /// This list is populated upon the creation of a Sema object.    
  IdentifierInfo* KnownFunctionIDs[id_num_known_functions];

  /// Translation Unit Scope - useful to Objective-C actions that need
  /// to lookup file scope declarations in the "ordinary" C decl namespace.
  /// For example, user-defined classes, built-in "id" type, etc.
  Scope *TUScope;

  /// The C++ "std" namespace, where the standard library resides. Cached here
  /// by GetStdNamespace
  NamespaceDecl *StdNamespace;

  /// A flag to remember whether the implicit forms of operator new and delete
  /// have been declared.
  bool GlobalNewDeleteDeclared;
  
  /// ObjCMethodList - a linked list of methods with different signatures.
  struct ObjCMethodList {
    ObjCMethodDecl *Method;
    ObjCMethodList *Next;
    
    ObjCMethodList() {
      Method = 0; 
      Next = 0;
    }
    ObjCMethodList(ObjCMethodDecl *M, ObjCMethodList *C) {
      Method = M;
      Next = C;
    }
  };
  /// Instance/Factory Method Pools - allows efficient lookup when typechecking
  /// messages to "id". We need to maintain a list, since selectors can have
  /// differing signatures across classes. In Cocoa, this happens to be 
  /// extremely uncommon (only 1% of selectors are "overloaded").
  llvm::DenseMap<Selector, ObjCMethodList> InstanceMethodPool;
  llvm::DenseMap<Selector, ObjCMethodList> FactoryMethodPool;
public:
  Sema(Preprocessor &pp, ASTContext &ctxt, ASTConsumer &consumer);
  ~Sema() {
    if (PackContext) FreePackedContext();
  }
  
  const LangOptions &getLangOptions() const { return LangOpts; }
  Diagnostic &getDiagnostics() const { return Diags; }
  SourceManager &getSourceManager() const { return SourceMgr; }

  /// The primitive diagnostic helpers.
  DiagnosticBuilder Diag(SourceLocation Loc, unsigned DiagID) {
    return Diags.Report(FullSourceLoc(Loc, SourceMgr), DiagID);
  }

  virtual void DeleteExpr(ExprTy *E);
  virtual void DeleteStmt(StmtTy *S);

  OwningExprResult Owned(Expr* E) { return OwningExprResult(*this, E); }
  OwningExprResult Owned(ExprResult R) {
    if (R.isInvalid())
      return ExprError();
    return OwningExprResult(*this, R.get());
  }
  OwningStmtResult Owned(Stmt* S) { return OwningStmtResult(*this, S); }

  virtual void ActOnEndOfTranslationUnit();

  //===--------------------------------------------------------------------===//
  // Type Analysis / Processing: SemaType.cpp.
  //
  QualType ConvertDeclSpecToType(const DeclSpec &DS);
  void ProcessTypeAttributeList(QualType &Result, const AttributeList *AL);
  QualType GetTypeForDeclarator(Declarator &D, Scope *S, unsigned Skip = 0);
  DeclarationName GetNameForDeclarator(Declarator &D);

  QualType ObjCGetTypeForMethodDefinition(DeclTy *D);

  bool UnwrapSimilarPointerTypes(QualType& T1, QualType& T2);

  virtual TypeResult ActOnTypeName(Scope *S, Declarator &D);

  bool DiagnoseIncompleteType(SourceLocation Loc, QualType T, unsigned diag,
                              SourceRange Range1 = SourceRange(),
                              SourceRange Range2 = SourceRange(),
                              QualType PrintType = QualType());

  //===--------------------------------------------------------------------===//
  // Symbol table / Decl tracking callbacks: SemaDecl.cpp.
  //
  virtual TypeTy *getTypeName(IdentifierInfo &II, SourceLocation NameLoc, 
                              Scope *S, const CXXScopeSpec *SS);
  virtual DeclTy *ActOnDeclarator(Scope *S, Declarator &D, DeclTy *LastInGroup){
    return ActOnDeclarator(S, D, LastInGroup, false);
  }
  DeclTy *ActOnDeclarator(Scope *S, Declarator &D, DeclTy *LastInGroup,
                          bool IsFunctionDefinition);
  NamedDecl* ActOnTypedefDeclarator(Scope* S, Declarator& D, DeclContext* DC,
                                    QualType R, Decl* LastDeclarator,
                                    Decl* PrevDecl, bool& InvalidDecl,
                                    bool &Redeclaration);
  void InjectLocallyScopedExternalDeclaration(ValueDecl *VD);
  NamedDecl* ActOnVariableDeclarator(Scope* S, Declarator& D, DeclContext* DC,
                                     QualType R, Decl* LastDeclarator,
                                     NamedDecl* PrevDecl, bool& InvalidDecl,
                                     bool &Redeclaration);
  NamedDecl* ActOnFunctionDeclarator(Scope* S, Declarator& D, DeclContext* DC,
                                     QualType R, Decl *LastDeclarator,
                                     NamedDecl* PrevDecl, 
                                     bool IsFunctionDefinition,
                                     bool& InvalidDecl, bool &Redeclaration);
  virtual DeclTy *ActOnParamDeclarator(Scope *S, Declarator &D);
  virtual void ActOnParamDefaultArgument(DeclTy *param, 
                                         SourceLocation EqualLoc,
                                         ExprTy *defarg);
  virtual void ActOnParamUnparsedDefaultArgument(DeclTy *param, 
                                                 SourceLocation EqualLoc);
  virtual void ActOnParamDefaultArgumentError(DeclTy *param);
  virtual void AddInitializerToDecl(DeclTy *dcl, ExprArg init);
  void AddInitializerToDecl(DeclTy *dcl, ExprArg init, bool DirectInit);
  void ActOnUninitializedDecl(DeclTy *dcl);
  virtual DeclTy *FinalizeDeclaratorGroup(Scope *S, DeclTy *Group);

  virtual void ActOnFinishKNRParamDeclarations(Scope *S, Declarator &D);
  virtual DeclTy *ActOnStartOfFunctionDef(Scope *S, Declarator &D);
  virtual DeclTy *ActOnStartOfFunctionDef(Scope *S, DeclTy *D);
  virtual void ObjCActOnStartOfMethodDef(Scope *S, DeclTy *D);

  virtual DeclTy *ActOnFinishFunctionBody(DeclTy *Decl, StmtArg Body);
  virtual DeclTy *ActOnFileScopeAsmDecl(SourceLocation Loc, ExprArg expr);

  /// Scope actions.
  virtual void ActOnPopScope(SourceLocation Loc, Scope *S);
  virtual void ActOnTranslationUnitScope(SourceLocation Loc, Scope *S);

  /// ParsedFreeStandingDeclSpec - This method is invoked when a declspec with
  /// no declarator (e.g. "struct foo;") is parsed.
  virtual DeclTy *ParsedFreeStandingDeclSpec(Scope *S, DeclSpec &DS);
  
  bool InjectAnonymousStructOrUnionMembers(Scope *S, DeclContext *Owner,
                                           RecordDecl *AnonRecord);
  virtual DeclTy *BuildAnonymousStructOrUnion(Scope *S, DeclSpec &DS, 
                                              RecordDecl *Record);

  virtual DeclTy *ActOnTag(Scope *S, unsigned TagSpec, TagKind TK,
                           SourceLocation KWLoc, const CXXScopeSpec &SS,
                           IdentifierInfo *Name, SourceLocation NameLoc,
                           AttributeList *Attr);
  
  virtual void ActOnDefs(Scope *S, DeclTy *TagD, SourceLocation DeclStart,
                         IdentifierInfo *ClassName,
                         llvm::SmallVectorImpl<DeclTy*> &Decls);
  virtual DeclTy *ActOnField(Scope *S, DeclTy *TagD, SourceLocation DeclStart,
                             Declarator &D, ExprTy *BitfieldWidth);
  
  virtual DeclTy *ActOnIvar(Scope *S, SourceLocation DeclStart,
                            Declarator &D, ExprTy *BitfieldWidth,
                            tok::ObjCKeywordKind visibility);

  // This is used for both record definitions and ObjC interface declarations.
  virtual void ActOnFields(Scope* S,
                           SourceLocation RecLoc, DeclTy *TagDecl,
                           DeclTy **Fields, unsigned NumFields,
                           SourceLocation LBrac, SourceLocation RBrac,
                           AttributeList *AttrList);

  /// ActOnTagStartDefinition - Invoked when we have entered the
  /// scope of a tag's definition (e.g., for an enumeration, class,
  /// struct, or union).
  virtual void ActOnTagStartDefinition(Scope *S, DeclTy *TagDecl);

  /// ActOnTagFinishDefinition - Invoked once we have finished parsing
  /// the definition of a tag (enumeration, class, struct, or union).
  virtual void ActOnTagFinishDefinition(Scope *S, DeclTy *TagDecl);

  virtual DeclTy *ActOnEnumConstant(Scope *S, DeclTy *EnumDecl,
                                    DeclTy *LastEnumConstant,
                                    SourceLocation IdLoc, IdentifierInfo *Id,
                                    SourceLocation EqualLoc, ExprTy *Val);
  virtual void ActOnEnumBody(SourceLocation EnumLoc, DeclTy *EnumDecl,
                             DeclTy **Elements, unsigned NumElements);

  DeclContext *getContainingDC(DeclContext *DC);

  /// Set the current declaration context until it gets popped.
  void PushDeclContext(Scope *S, DeclContext *DC);
  void PopDeclContext();
  
  /// getCurFunctionDecl - If inside of a function body, this returns a pointer
  /// to the function decl for the function being parsed.  If we're currently
  /// in a 'block', this returns the containing context.
  FunctionDecl *getCurFunctionDecl();
  
  /// getCurMethodDecl - If inside of a method body, this returns a pointer to
  /// the method decl for the method being parsed.  If we're currently
  /// in a 'block', this returns the containing context.
  ObjCMethodDecl *getCurMethodDecl();

  /// getCurFunctionOrMethodDecl - Return the Decl for the current ObjC method
  /// or C function we're in, otherwise return null.  If we're currently
  /// in a 'block', this returns the containing context.
  NamedDecl *getCurFunctionOrMethodDecl();

  /// Add this decl to the scope shadowed decl chains.
  void PushOnScopeChains(NamedDecl *D, Scope *S);

  /// isDeclInScope - If 'Ctx' is a function/method, isDeclInScope returns true
  /// if 'D' is in Scope 'S', otherwise 'S' is ignored and isDeclInScope returns
  /// true if 'D' belongs to the given declaration context.
  bool isDeclInScope(Decl *D, DeclContext *Ctx, Scope *S = 0) {
    return IdResolver.isDeclInScope(D, Ctx, Context, S);
  }

  /// Subroutines of ActOnDeclarator().
  TypedefDecl *ParseTypedefDecl(Scope *S, Declarator &D, QualType T,
                                Decl *LastDecl);
  bool MergeTypeDefDecl(TypedefDecl *New, Decl *Old);
  bool MergeFunctionDecl(FunctionDecl *New, Decl *Old);
  bool MergeCompatibleFunctionDecls(FunctionDecl *New, FunctionDecl *Old);
  bool MergeVarDecl(VarDecl *New, Decl *Old);
  bool MergeCXXFunctionDecl(FunctionDecl *New, FunctionDecl *Old);
  void CheckForFileScopedRedefinitions(Scope *S, VarDecl *VD);

  /// C++ Overloading.
  bool IsOverload(FunctionDecl *New, Decl* OldD, 
                  OverloadedFunctionDecl::function_iterator &MatchedDecl);
  ImplicitConversionSequence 
  TryImplicitConversion(Expr* From, QualType ToType,
                        bool SuppressUserConversions = false,
                        bool AllowExplicit = false);
  bool IsStandardConversion(Expr *From, QualType ToType, 
                            StandardConversionSequence& SCS);
  bool IsIntegralPromotion(Expr *From, QualType FromType, QualType ToType);
  bool IsFloatingPointPromotion(QualType FromType, QualType ToType);
  bool IsComplexPromotion(QualType FromType, QualType ToType);
  bool IsPointerConversion(Expr *From, QualType FromType, QualType ToType,
                           QualType& ConvertedType, bool &IncompatibleObjC);
  bool isObjCPointerConversion(QualType FromType, QualType ToType,
                               QualType& ConvertedType, bool &IncompatibleObjC);
  bool CheckPointerConversion(Expr *From, QualType ToType);
  bool IsMemberPointerConversion(Expr *From, QualType FromType, QualType ToType,
                                 QualType &ConvertedType);
  bool CheckMemberPointerConversion(Expr *From, QualType ToType);
  bool IsQualificationConversion(QualType FromType, QualType ToType);
  bool IsUserDefinedConversion(Expr *From, QualType ToType, 
                               UserDefinedConversionSequence& User,
                               bool AllowConversionFunctions,
                               bool AllowExplicit);

  ImplicitConversionSequence::CompareKind 
  CompareImplicitConversionSequences(const ImplicitConversionSequence& ICS1,
                                     const ImplicitConversionSequence& ICS2);

  ImplicitConversionSequence::CompareKind 
  CompareStandardConversionSequences(const StandardConversionSequence& SCS1,
                                     const StandardConversionSequence& SCS2);

  ImplicitConversionSequence::CompareKind 
  CompareQualificationConversions(const StandardConversionSequence& SCS1,
                                  const StandardConversionSequence& SCS2);

  ImplicitConversionSequence::CompareKind
  CompareDerivedToBaseConversions(const StandardConversionSequence& SCS1,
                                  const StandardConversionSequence& SCS2);

  ImplicitConversionSequence 
  TryCopyInitialization(Expr* From, QualType ToType,
                        bool SuppressUserConversions = false);
  bool PerformCopyInitialization(Expr *&From, QualType ToType, 
                                 const char *Flavor);

  ImplicitConversionSequence
  TryObjectArgumentInitialization(Expr *From, CXXMethodDecl *Method);
  bool PerformObjectArgumentInitialization(Expr *&From, CXXMethodDecl *Method);

  ImplicitConversionSequence TryContextuallyConvertToBool(Expr *From);
  bool PerformContextuallyConvertToBool(Expr *&From);

  /// OverloadingResult - Capture the result of performing overload
  /// resolution.
  enum OverloadingResult {
    OR_Success,             ///< Overload resolution succeeded.
    OR_No_Viable_Function,  ///< No viable function found.
    OR_Ambiguous,           ///< Ambiguous candidates found.
    OR_Deleted              ///< Overload resoltuion refers to a deleted function.
  };

  void AddOverloadCandidate(FunctionDecl *Function, 
                            Expr **Args, unsigned NumArgs,
                            OverloadCandidateSet& CandidateSet,
                            bool SuppressUserConversions = false);
  void AddMethodCandidate(CXXMethodDecl *Method,
                          Expr *Object, Expr **Args, unsigned NumArgs,
                          OverloadCandidateSet& CandidateSet,
                          bool SuppressUserConversions = false);
  void AddConversionCandidate(CXXConversionDecl *Conversion,
                              Expr *From, QualType ToType,
                              OverloadCandidateSet& CandidateSet);
  void AddSurrogateCandidate(CXXConversionDecl *Conversion,
                             const FunctionTypeProto *Proto,
                             Expr *Object, Expr **Args, unsigned NumArgs,
                             OverloadCandidateSet& CandidateSet);
  bool AddOperatorCandidates(OverloadedOperatorKind Op, Scope *S,
                             SourceLocation OpLoc,
                             Expr **Args, unsigned NumArgs,
                             OverloadCandidateSet& CandidateSet,
                             SourceRange OpRange = SourceRange());
  void AddBuiltinCandidate(QualType ResultTy, QualType *ParamTys, 
                           Expr **Args, unsigned NumArgs,
                           OverloadCandidateSet& CandidateSet,
                           bool IsAssignmentOperator = false,
                           unsigned NumContextualBoolArguments = 0);
  void AddBuiltinOperatorCandidates(OverloadedOperatorKind Op, 
                                    Expr **Args, unsigned NumArgs, 
                                    OverloadCandidateSet& CandidateSet);
  void AddArgumentDependentLookupCandidates(DeclarationName Name,
                                            Expr **Args, unsigned NumArgs,
                                            OverloadCandidateSet& CandidateSet);
  bool isBetterOverloadCandidate(const OverloadCandidate& Cand1,
                                 const OverloadCandidate& Cand2);
  OverloadingResult BestViableFunction(OverloadCandidateSet& CandidateSet,
                                       OverloadCandidateSet::iterator& Best);
  void PrintOverloadCandidates(OverloadCandidateSet& CandidateSet,
                               bool OnlyViable);
                               
  FunctionDecl *ResolveAddressOfOverloadedFunction(Expr *From, QualType ToType,
                                                   bool Complain);
  void FixOverloadedFunctionReference(Expr *E, FunctionDecl *Fn);

  FunctionDecl *ResolveOverloadedCallFn(Expr *Fn, NamedDecl *Callee,
                                        DeclarationName UnqualifiedName,
                                        SourceLocation LParenLoc,
                                        Expr **Args, unsigned NumArgs,
                                        SourceLocation *CommaLocs, 
                                        SourceLocation RParenLoc,
                                        bool &ArgumentDependentLookup);
  ExprResult
  BuildCallToMemberFunction(Scope *S, Expr *MemExpr,
                            SourceLocation LParenLoc, Expr **Args, 
                            unsigned NumArgs, SourceLocation *CommaLocs,
                            SourceLocation RParenLoc);
  ExprResult 
  BuildCallToObjectOfClassType(Scope *S, Expr *Object, SourceLocation LParenLoc,
                               Expr **Args, unsigned NumArgs,
                               SourceLocation *CommaLocs, 
                               SourceLocation RParenLoc);

  ExprResult BuildOverloadedArrowExpr(Scope *S, Expr *Base, SourceLocation OpLoc,
                                      SourceLocation MemberLoc,
                                      IdentifierInfo &Member);
               
  /// Helpers for dealing with function parameters.
  bool CheckParmsForFunctionDef(FunctionDecl *FD);
  void CheckCXXDefaultArguments(FunctionDecl *FD);
  void CheckExtraCXXDefaultArguments(Declarator &D);

  Scope *getNonFieldDeclScope(Scope *S);

  /// \name Name lookup
  ///
  /// These routines provide name lookup that is used during semantic
  /// analysis to resolve the various kinds of names (identifiers,
  /// overloaded operator names, constructor names, etc.) into zero or
  /// more declarations within a particular scope. The major entry
  /// points are LookupName, which performs unqualified name lookup,
  /// and LookupQualifiedName, which performs qualified name lookup. 
  ///
  /// All name lookup is performed based on some specific criteria,
  /// which specify what names will be visible to name lookup and how
  /// far name lookup should work. These criteria are important both
  /// for capturing language semantics (certain lookups will ignore
  /// certain names, for example) and for performance, since name
  /// lookup is often a bottleneck in the compilation of C++. Name
  /// lookup criteria is specified via the LookupCriteria enumeration.
  ///
  /// The results of name lookup can vary based on the kind of name
  /// lookup performed, the current language, and the translation
  /// unit. In C, for example, name lookup will either return nothing
  /// (no entity found) or a single declaration. In C++, name lookup
  /// can additionally refer to a set of overloaded functions or
  /// result in an ambiguity. All of the possible results of name
  /// lookup are captured by the LookupResult class, which provides
  /// the ability to distinguish among them.
  //@{

  /// @brief Describes the kind of name lookup to perform.
  enum LookupNameKind {
    /// Ordinary name lookup, which finds ordinary names (functions,
    /// variables, typedefs, etc.) in C and most kinds of names
    /// (functions, variables, members, types, etc.) in C++.
    LookupOrdinaryName = 0,
    /// Tag name lookup, which finds the names of enums, classes,
    /// structs, and unions.
    LookupTagName,
    /// Member name lookup, which finds the names of
    /// class/struct/union members.
    LookupMemberName,
    // Look up of an operator name (e.g., operator+) for use with
    // operator overloading. This lookup is similar to ordinary name
    // lookup, but will ignore any declarations that are class
    // members.
    LookupOperatorName,
    /// Look up of a name that precedes the '::' scope resolution
    /// operator in C++. This lookup completely ignores operator,
    /// function, and enumerator names (C++ [basic.lookup.qual]p1).
    LookupNestedNameSpecifierName,
    /// Look up a namespace name within a C++ using directive or
    /// namespace alias definition, ignoring non-namespace names (C++
    /// [basic.lookup.udir]p1).
    LookupNamespaceName,
    // Look up an ordinary name that is going to be redeclared as a
    // name with linkage. This lookup ignores any declarations that
    // are outside of the current scope unless they have linkage. See 
    // C99 6.2.2p4-5 and C++ [basic.link]p6.
    LookupRedeclarationWithLinkage
  };

  /// @brief Represents the results of name lookup.
  ///
  /// An instance of the LookupResult class captures the results of a
  /// single name lookup, which can return no result (nothing found),
  /// a single declaration, a set of overloaded functions, or an
  /// ambiguity. Use the getKind() method to determine which of these
  /// results occurred for a given lookup. 
  ///
  /// Any non-ambiguous lookup can be converted into a single
  /// (possibly NULL) @c NamedDecl* via a conversion function or the
  /// getAsDecl() method. This conversion permits the common-case
  /// usage in C and Objective-C where name lookup will always return
  /// a single declaration.
  struct LookupResult {
    /// The kind of entity that is actually stored within the
    /// LookupResult object.
    enum {
      /// First is a single declaration (a NamedDecl*), which may be NULL.
      SingleDecl,

      /// First is a single declaration (an OverloadedFunctionDecl*).
      OverloadedDeclSingleDecl,

      /// [First, Last) is an iterator range represented as opaque
      /// pointers used to reconstruct IdentifierResolver::iterators.
      OverloadedDeclFromIdResolver,

      /// [First, Last) is an iterator range represented as opaque
      /// pointers used to reconstruct DeclContext::lookup_iterators.
      OverloadedDeclFromDeclContext,

      /// First is a pointer to a BasePaths structure, which is owned
      /// by the LookupResult. Last is non-zero to indicate that the
      /// ambiguity is caused by two names found in base class
      /// subobjects of different types.
      AmbiguousLookupStoresBasePaths,

      /// [First, Last) is an iterator range represented as opaque
      /// pointers used to reconstruct new'ed Decl*[] array containing
      /// found ambiguous decls. LookupResult is owner of this array.
      AmbiguousLookupStoresDecls

    } StoredKind;

    /// The first lookup result, whose contents depend on the kind of
    /// lookup result. This may be a NamedDecl* (if StoredKind ==
    /// SingleDecl), OverloadedFunctionDecl* (if StoredKind ==
    /// OverloadedDeclSingleDecl), the opaque pointer from an
    /// IdentifierResolver::iterator (if StoredKind ==
    /// OverloadedDeclFromIdResolver), a DeclContext::lookup_iterator
    /// (if StoredKind == OverloadedDeclFromDeclContext), or a
    /// BasePaths pointer (if StoredKind == AmbiguousLookupStoresBasePaths).
    mutable uintptr_t First;

    /// The last lookup result, whose contents depend on the kind of
    /// lookup result. This may be unused (if StoredKind ==
    /// SingleDecl), it may have the same type as First (for
    /// overloaded function declarations), or is may be used as a
    /// Boolean value (if StoredKind == AmbiguousLookupStoresBasePaths).
    mutable uintptr_t Last;

    /// Context - The context in which we will build any
    /// OverloadedFunctionDecl nodes needed by the conversion to
    /// Decl*.
    ASTContext *Context;

    /// @brief The kind of entity found by name lookup.
    enum LookupKind {
      /// @brief No entity found met the criteria.
      NotFound = 0,

      /// @brief Name lookup found a single declaration that met the
      /// criteria. getAsDecl will return this declaration.
      Found,

      /// @brief Name lookup found a set of overloaded functions that
      /// met the criteria. getAsDecl will turn this set of overloaded
      /// functions into an OverloadedFunctionDecl.
      FoundOverloaded,

      /// Name lookup results in an ambiguity because multiple
      /// entities that meet the lookup criteria were found in
      /// subobjects of different types. For example:
      /// @code
      /// struct A { void f(int); }
      /// struct B { void f(double); }
      /// struct C : A, B { };
      /// void test(C c) { 
      ///   c.f(0); // error: A::f and B::f come from subobjects of different
      ///           // types. overload resolution is not performed.
      /// }
      /// @endcode
      AmbiguousBaseSubobjectTypes,

      /// Name lookup results in an ambiguity because multiple
      /// nonstatic entities that meet the lookup criteria were found
      /// in different subobjects of the same type. For example:
      /// @code
      /// struct A { int x; };
      /// struct B : A { };
      /// struct C : A { };
      /// struct D : B, C { };
      /// int test(D d) {
      ///   return d.x; // error: 'x' is found in two A subobjects (of B and C)
      /// }
      /// @endcode
      AmbiguousBaseSubobjects,

      /// Name lookup results in an ambiguity because multiple definitions
      /// of entity that meet the lookup criteria were found in different
      /// declaration contexts.
      /// @code
      /// namespace A {
      ///   int i;
      ///   namespace B { int i; }
      ///   int test() {
      ///     using namespace B;
      ///     return i; // error 'i' is found in namespace A and A::B
      ///    }
      /// }
      /// @endcode
      AmbiguousReference
    };

    static LookupResult CreateLookupResult(ASTContext &Context, NamedDecl *D);

    static LookupResult CreateLookupResult(ASTContext &Context, 
                                           IdentifierResolver::iterator F, 
                                           IdentifierResolver::iterator L);

    static LookupResult CreateLookupResult(ASTContext &Context, 
                                           DeclContext::lookup_iterator F, 
                                           DeclContext::lookup_iterator L);

    static LookupResult CreateLookupResult(ASTContext &Context, BasePaths *Paths, 
                                           bool DifferentSubobjectTypes) {
      LookupResult Result;
      Result.StoredKind = AmbiguousLookupStoresBasePaths;
      Result.First = reinterpret_cast<uintptr_t>(Paths);
      Result.Last = DifferentSubobjectTypes? 1 : 0;
      Result.Context = &Context;
      return Result;
    }

    template <typename Iterator>
    static LookupResult CreateLookupResult(ASTContext &Context,
                                           Iterator B, std::size_t Len) {
      NamedDecl ** Array = new NamedDecl*[Len];
      for (std::size_t Idx = 0; Idx < Len; ++Idx, ++B)
        Array[Idx] = *B;
      LookupResult Result;
      Result.StoredKind = AmbiguousLookupStoresDecls;
      Result.First = reinterpret_cast<uintptr_t>(Array);
      Result.Last = reinterpret_cast<uintptr_t>(Array + Len);
      Result.Context = &Context;
      return Result;
    }

    LookupKind getKind() const;

    /// @brief Determine whether name look found something.
    operator bool() const { return getKind() != NotFound; }

    /// @brief Determines whether the lookup resulted in an ambiguity.
    bool isAmbiguous() const {
      return StoredKind == AmbiguousLookupStoresBasePaths ||
             StoredKind == AmbiguousLookupStoresDecls;
    }

    /// @brief Allows conversion of a lookup result into a
    /// declaration, with the same behavior as getAsDecl.
    operator NamedDecl*() const { return getAsDecl(); }

    NamedDecl* getAsDecl() const;

    BasePaths *getBasePaths() const;

    /// \brief Iterate over the results of name lookup.
    ///
    /// The @c iterator class provides iteration over the results of a
    /// non-ambiguous name lookup.
    class iterator {
      /// The LookupResult structure we're iterating through.
      LookupResult *Result;

      /// The current position of this iterator within the sequence of
      /// results. This value will have the same representation as the
      /// @c First field in the LookupResult structure.
      mutable uintptr_t Current;

    public:
      typedef NamedDecl *                value_type;
      typedef NamedDecl *                reference;
      typedef NamedDecl *                pointer;
      typedef std::ptrdiff_t             difference_type;
      typedef std::forward_iterator_tag  iterator_category;

      iterator() : Result(0), Current(0) { }

      iterator(LookupResult *Res, uintptr_t Cur) : Result(Res), Current(Cur) { }

      reference operator*() const;

      pointer operator->() const { return **this; }

      iterator &operator++();

      iterator operator++(int) {
        iterator tmp(*this);
        ++(*this);
        return tmp;
      }

      friend inline bool operator==(iterator const& x, iterator const& y) {
        return x.Current == y.Current;
      }

      friend inline bool operator!=(iterator const& x, iterator const& y) {
        return x.Current != y.Current;
      }
    };
    friend class iterator;

    iterator begin();
    iterator end();
  };

private:
  typedef llvm::SmallVector<LookupResult, 3> LookupResultsVecTy;

  std::pair<bool, LookupResult> CppLookupName(Scope *S, DeclarationName Name,
                                              LookupNameKind NameKind,
                                              bool RedeclarationOnly);

public:
  /// Determines whether D is a suitable lookup result according to the
  /// lookup criteria.
  static bool isAcceptableLookupResult(NamedDecl *D, LookupNameKind NameKind,
                                       unsigned IDNS) {
    switch (NameKind) {
    case Sema::LookupOrdinaryName:
    case Sema::LookupTagName:
    case Sema::LookupMemberName:
    case Sema::LookupRedeclarationWithLinkage: // FIXME: check linkage, scoping
      return D->isInIdentifierNamespace(IDNS);
      
    case Sema::LookupOperatorName:
      return D->isInIdentifierNamespace(IDNS) && 
             !D->getDeclContext()->isRecord();

    case Sema::LookupNestedNameSpecifierName:
      return isa<TypedefDecl>(D) || D->isInIdentifierNamespace(Decl::IDNS_Tag);
      
    case Sema::LookupNamespaceName:
      return isa<NamespaceDecl>(D);
    }
    
    assert(false && 
           "isAcceptableLookupResult always returns before this point");
    return false;
  }

  LookupResult LookupName(Scope *S, DeclarationName Name, 
                          LookupNameKind NameKind, 
                          bool RedeclarationOnly = false,
                          bool AllowBuiltinCreation = true,
                          SourceLocation Loc = SourceLocation());
  LookupResult LookupQualifiedName(DeclContext *LookupCtx, DeclarationName Name,
                                   LookupNameKind NameKind, 
                                   bool RedeclarationOnly = false);
  LookupResult LookupParsedName(Scope *S, const CXXScopeSpec *SS, 
                                DeclarationName Name,
                                LookupNameKind NameKind, 
                                bool RedeclarationOnly = false,
                                bool AllowBuiltinCreation = true,
                                SourceLocation Loc = SourceLocation());
  
  typedef llvm::SmallPtrSet<NamespaceDecl *, 16> AssociatedNamespaceSet;
  typedef llvm::SmallPtrSet<CXXRecordDecl *, 16> AssociatedClassSet;

  void FindAssociatedClassesAndNamespaces(Expr **Args, unsigned NumArgs,
                                   AssociatedNamespaceSet &AssociatedNamespaces,
                                   AssociatedClassSet &AssociatedClasses);

  bool DiagnoseAmbiguousLookup(LookupResult &Result, DeclarationName Name,
                               SourceLocation NameLoc, 
                               SourceRange LookupRange = SourceRange());
  //@}
  
  ObjCInterfaceDecl *getObjCInterfaceDecl(IdentifierInfo *Id);
  NamedDecl *LazilyCreateBuiltin(IdentifierInfo *II, unsigned ID, 
                                 Scope *S, bool ForRedeclaration,
                                 SourceLocation Loc);
  NamedDecl *ImplicitlyDefineFunction(SourceLocation Loc, IdentifierInfo &II,
                                      Scope *S);
  void AddKnownFunctionAttributes(FunctionDecl *FD);

  // More parsing and symbol table subroutines.

  // Decl attributes - this routine is the top level dispatcher. 
  void ProcessDeclAttributes(Decl *D, const Declarator &PD);
  void ProcessDeclAttributeList(Decl *D, const AttributeList *AttrList);

  void WarnUndefinedMethod(SourceLocation ImpLoc, ObjCMethodDecl *method,
                           bool &IncompleteImpl);
  void WarnConflictingTypedMethods(ObjCMethodDecl *ImpMethod,
                                   ObjCMethodDecl *IntfMethod);

  NamespaceDecl *GetStdNamespace();
  
  bool isPropertyReadonly(ObjCPropertyDecl *PropertyDecl,
                          ObjCInterfaceDecl *IDecl) const;
                           
  /// CheckProtocolMethodDefs - This routine checks unimplemented
  /// methods declared in protocol, and those referenced by it.
  /// \param IDecl - Used for checking for methods which may have been
  /// inherited.
  void CheckProtocolMethodDefs(SourceLocation ImpLoc,
                               ObjCProtocolDecl *PDecl,
                               bool& IncompleteImpl,
                               const llvm::DenseSet<Selector> &InsMap,
                               const llvm::DenseSet<Selector> &ClsMap,
                               ObjCInterfaceDecl *IDecl);
  
  /// CheckImplementationIvars - This routine checks if the instance variables
  /// listed in the implelementation match those listed in the interface. 
  void CheckImplementationIvars(ObjCImplementationDecl *ImpDecl,
                                ObjCIvarDecl **Fields, unsigned nIvars,
                                SourceLocation Loc);
  
  /// ImplMethodsVsClassMethods - This is main routine to warn if any method
  /// remains unimplemented in the @implementation class.
  void ImplMethodsVsClassMethods(ObjCImplementationDecl* IMPDecl, 
                                 ObjCInterfaceDecl* IDecl);
  
  /// ImplCategoryMethodsVsIntfMethods - Checks that methods declared in the
  /// category interface is implemented in the category @implementation.
  void ImplCategoryMethodsVsIntfMethods(ObjCCategoryImplDecl *CatImplDecl,
                                        ObjCCategoryDecl *CatClassDecl);
  /// MatchTwoMethodDeclarations - Checks if two methods' type match and returns
  /// true, or false, accordingly.
  bool MatchTwoMethodDeclarations(const ObjCMethodDecl *Method, 
                                  const ObjCMethodDecl *PrevMethod,
                                  bool matchBasedOnSizeAndAlignment = false); 

  /// AddInstanceMethodToGlobalPool - All instance methods in a translation
  /// unit are added to a global pool. This allows us to efficiently associate
  /// a selector with a method declaraation for purposes of typechecking
  /// messages sent to "id" (where the class of the object is unknown).
  void AddInstanceMethodToGlobalPool(ObjCMethodDecl *Method);
  
  /// LookupInstanceMethodInGlobalPool - Returns the method and warns if
  /// there are multiple signatures.
  ObjCMethodDecl *LookupInstanceMethodInGlobalPool(Selector Sel, SourceRange R);
  
  /// AddFactoryMethodToGlobalPool - Same as above, but for factory methods.
  void AddFactoryMethodToGlobalPool(ObjCMethodDecl *Method);
  //===--------------------------------------------------------------------===//
  // Statement Parsing Callbacks: SemaStmt.cpp.
public:
  virtual OwningStmtResult ActOnExprStmt(ExprArg Expr);

  virtual OwningStmtResult ActOnNullStmt(SourceLocation SemiLoc);
  virtual OwningStmtResult ActOnCompoundStmt(SourceLocation L, SourceLocation R,
                                             MultiStmtArg Elts,
                                             bool isStmtExpr);
  virtual OwningStmtResult ActOnDeclStmt(DeclTy *Decl, SourceLocation StartLoc,
                                         SourceLocation EndLoc);
  virtual OwningStmtResult ActOnCaseStmt(SourceLocation CaseLoc, ExprArg LHSVal,
                                    SourceLocation DotDotDotLoc, ExprArg RHSVal,
                                    SourceLocation ColonLoc, StmtArg SubStmt);
  virtual OwningStmtResult ActOnDefaultStmt(SourceLocation DefaultLoc,
                                            SourceLocation ColonLoc,
                                            StmtArg SubStmt, Scope *CurScope);
  virtual OwningStmtResult ActOnLabelStmt(SourceLocation IdentLoc,
                                          IdentifierInfo *II,
                                          SourceLocation ColonLoc,
                                          StmtArg SubStmt);
  virtual OwningStmtResult ActOnIfStmt(SourceLocation IfLoc, ExprArg CondVal,
                                       StmtArg ThenVal, SourceLocation ElseLoc,
                                       StmtArg ElseVal);
  virtual OwningStmtResult ActOnStartOfSwitchStmt(ExprArg Cond);
  virtual OwningStmtResult ActOnFinishSwitchStmt(SourceLocation SwitchLoc,
                                                 StmtArg Switch, StmtArg Body);
  virtual OwningStmtResult ActOnWhileStmt(SourceLocation WhileLoc, ExprArg Cond,
                                          StmtArg Body);
  virtual OwningStmtResult ActOnDoStmt(SourceLocation DoLoc, StmtArg Body,
                                       SourceLocation WhileLoc, ExprArg Cond);

  virtual OwningStmtResult ActOnForStmt(SourceLocation ForLoc,
                                        SourceLocation LParenLoc,
                                        StmtArg First, ExprArg Second,
                                        ExprArg Third, SourceLocation RParenLoc,
                                        StmtArg Body);
  virtual OwningStmtResult ActOnObjCForCollectionStmt(SourceLocation ForColLoc,
                                       SourceLocation LParenLoc,
                                       StmtArg First, ExprArg Second,
                                       SourceLocation RParenLoc, StmtArg Body);

  virtual OwningStmtResult ActOnGotoStmt(SourceLocation GotoLoc,
                                         SourceLocation LabelLoc,
                                         IdentifierInfo *LabelII);
  virtual OwningStmtResult ActOnIndirectGotoStmt(SourceLocation GotoLoc,
                                                 SourceLocation StarLoc,
                                                 ExprArg DestExp);
  virtual OwningStmtResult ActOnContinueStmt(SourceLocation ContinueLoc,
                                             Scope *CurScope);
  virtual OwningStmtResult ActOnBreakStmt(SourceLocation GotoLoc,
                                          Scope *CurScope);

  virtual OwningStmtResult ActOnReturnStmt(SourceLocation ReturnLoc,
                                           ExprArg RetValExp);
  OwningStmtResult ActOnBlockReturnStmt(SourceLocation ReturnLoc,
                                        Expr *RetValExp);

  virtual OwningStmtResult ActOnAsmStmt(SourceLocation AsmLoc,
                                        bool IsSimple,
                                        bool IsVolatile,
                                        unsigned NumOutputs,
                                        unsigned NumInputs,
                                        std::string *Names,
                                        MultiExprArg Constraints,