contrib/llvm/tools/clang/lib/Index/Analyzer.cpp

   1 //===--- Analyzer.cpp - Analysis for indexing information -------*- 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 implements the Analyzer interface.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/Index/Analyzer.h"
  15 #include "clang/Index/Entity.h"
  16 #include "clang/Index/TranslationUnit.h"
  17 #include "clang/Index/Handlers.h"
  18 #include "clang/Index/ASTLocation.h"
  19 #include "clang/Index/GlobalSelector.h"
  20 #include "clang/Index/DeclReferenceMap.h"
  21 #include "clang/Index/SelectorMap.h"
  22 #include "clang/Index/IndexProvider.h"
  23 #include "clang/AST/DeclObjC.h"
  24 #include "clang/AST/ExprObjC.h"
  25 #include "llvm/ADT/SmallSet.h"
  26 using namespace clang;
  27 using namespace idx;
  28
  29 namespace  {
  30
  31 //===----------------------------------------------------------------------===//
  32 // DeclEntityAnalyzer Implementation
  33 //===----------------------------------------------------------------------===//
  34
  35 class DeclEntityAnalyzer : public TranslationUnitHandler {
  36   Entity Ent;
  37   TULocationHandler &TULocHandler;
  38
  39 public:
  40   DeclEntityAnalyzer(Entity ent, TULocationHandler &handler)
  41     : Ent(ent), TULocHandler(handler) { }
  42
  43   virtual void Handle(TranslationUnit *TU) {
  44     assert(TU && "Passed null translation unit");
  45
  46     Decl *D = Ent.getDecl(TU->getASTContext());
  47     assert(D && "Couldn't resolve Entity");
  48
  49     for (Decl::redecl_iterator I = D->redecls_begin(),
  50                                E = D->redecls_end(); I != E; ++I)
  51       TULocHandler.Handle(TULocation(TU, ASTLocation(*I)));
  52   }
  53 };
  54
  55 //===----------------------------------------------------------------------===//
  56 // RefEntityAnalyzer Implementation
  57 //===----------------------------------------------------------------------===//
  58
  59 class RefEntityAnalyzer : public TranslationUnitHandler {
  60   Entity Ent;
  61   TULocationHandler &TULocHandler;
  62
  63 public:
  64   RefEntityAnalyzer(Entity ent, TULocationHandler &handler)
  65     : Ent(ent), TULocHandler(handler) { }
  66
  67   virtual void Handle(TranslationUnit *TU) {
  68     assert(TU && "Passed null translation unit");
  69
  70     Decl *D = Ent.getDecl(TU->getASTContext());
  71     assert(D && "Couldn't resolve Entity");
  72     NamedDecl *ND = dyn_cast<NamedDecl>(D);
  73     if (!ND)
  74       return;
  75
  76     DeclReferenceMap &RefMap = TU->getDeclReferenceMap();
  77     for (DeclReferenceMap::astlocation_iterator
  78            I = RefMap.refs_begin(ND), E = RefMap.refs_end(ND); I != E; ++I)
  79       TULocHandler.Handle(TULocation(TU, *I));
  80   }
  81 };
  82
  83 //===----------------------------------------------------------------------===//
  84 // RefSelectorAnalyzer Implementation
  85 //===----------------------------------------------------------------------===//
  86
  87 /// \brief Accepts an ObjC method and finds all message expressions that this
  88 /// method may respond to.
  89 class RefSelectorAnalyzer : public TranslationUnitHandler {
  90   Program &Prog;
  91   TULocationHandler &TULocHandler;
  92
  93   // The original ObjCInterface associated with the method.
  94   Entity IFaceEnt;
  95   GlobalSelector GlobSel;
  96   bool IsInstanceMethod;
  97
  98   /// \brief Super classes of the ObjCInterface.
  99   typedef llvm::SmallSet<Entity, 16> EntitiesSetTy;
 100   EntitiesSetTy HierarchyEntities;
 101
 102 public:
 103   RefSelectorAnalyzer(ObjCMethodDecl *MD,
 104                       Program &prog, TULocationHandler &handler)
 105     : Prog(prog), TULocHandler(handler) {
 106     assert(MD);
 107
 108     // FIXME: Protocol methods.
 109     assert(!isa<ObjCProtocolDecl>(MD->getDeclContext()) &&
 110            "Protocol methods not supported yet");
 111
 112     ObjCInterfaceDecl *IFD = MD->getClassInterface();
 113     assert(IFD);
 114     IFaceEnt = Entity::get(IFD, Prog);
 115     GlobSel = GlobalSelector::get(MD->getSelector(), Prog);
 116     IsInstanceMethod = MD->isInstanceMethod();
 117
 118     for (ObjCInterfaceDecl *Cls = IFD->getSuperClass();
 119            Cls; Cls = Cls->getSuperClass())
 120       HierarchyEntities.insert(Entity::get(Cls, Prog));
 121   }
 122
 123   virtual void Handle(TranslationUnit *TU) {
 124     assert(TU && "Passed null translation unit");
 125
 126     ASTContext &Ctx = TU->getASTContext();
 127     // Null means it doesn't exist in this translation unit.
 128     ObjCInterfaceDecl *IFace =
 129         cast_or_null<ObjCInterfaceDecl>(IFaceEnt.getDecl(Ctx));
 130     Selector Sel = GlobSel.getSelector(Ctx);
 131
 132     SelectorMap &SelMap = TU->getSelectorMap();
 133     for (SelectorMap::astlocation_iterator
 134            I = SelMap.refs_begin(Sel), E = SelMap.refs_end(Sel); I != E; ++I) {
 135       if (ValidReference(*I, IFace))
 136         TULocHandler.Handle(TULocation(TU, *I));
 137     }
 138   }
 139
 140   /// \brief Determines whether the given message expression is likely to end
 141   /// up at the given interface decl.
 142   ///
 143   /// It returns true "eagerly", meaning it will return false only if it can
 144   /// "prove" statically that the interface cannot accept this message.
 145   bool ValidReference(ASTLocation ASTLoc, ObjCInterfaceDecl *IFace) {
 146     assert(ASTLoc.isStmt());
 147
 148     // FIXME: Finding @selector references should be through another Analyzer
 149     // method, like FindSelectors.
 150     if (isa<ObjCSelectorExpr>(ASTLoc.AsStmt()))
 151       return false;
 152
 153     ObjCInterfaceDecl *MsgD = 0;
 154     ObjCMessageExpr *Msg = cast<ObjCMessageExpr>(ASTLoc.AsStmt());
 155
 156     switch (Msg->getReceiverKind()) {
 157     case ObjCMessageExpr::Instance: {
 158       const ObjCObjectPointerType *OPT =
 159           Msg->getInstanceReceiver()->getType()->getAsObjCInterfacePointerType();
 160
 161       // Can be anything! Accept it as a possibility..
 162       if (!OPT || OPT->isObjCIdType() || OPT->isObjCQualifiedIdType())
 163         return true;
 164
 165       // Expecting class method.
 166       if (OPT->isObjCClassType() || OPT->isObjCQualifiedClassType())
 167         return !IsInstanceMethod;
 168
 169       MsgD = OPT->getInterfaceDecl();
 170       assert(MsgD);
 171
 172       // Should be an instance method.
 173       if (!IsInstanceMethod)
 174         return false;
 175       break;
 176     }
 177
 178     case ObjCMessageExpr::Class: {
 179       // Expecting class method.
 180       if (IsInstanceMethod)
 181         return false;
 182
 183       MsgD = Msg->getClassReceiver()->getAs<ObjCObjectType>()->getInterface();
 184       break;
 185     }
 186
 187     case ObjCMessageExpr::SuperClass:
 188       // Expecting class method.
 189       if (IsInstanceMethod)
 190         return false;
 191
 192       MsgD = Msg->getSuperType()->getAs<ObjCObjectType>()->getInterface();
 193       break;
 194
 195     case ObjCMessageExpr::SuperInstance:
 196       // Expecting instance method.
 197       if (!IsInstanceMethod)
 198         return false;
 199
 200       MsgD = Msg->getSuperType()->getAs<ObjCObjectPointerType>()
 201                                                           ->getInterfaceDecl();
 202       break;
 203     }
 204
 205     assert(MsgD);
 206
 207     // Same interface ? We have a winner!
 208     if (MsgD == IFace)
 209       return true;
 210
 211     // If the message interface is a superclass of the original interface,
 212     // accept this message as a possibility.
 213     if (HierarchyEntities.count(Entity::get(MsgD, Prog)))
 214       return true;
 215
 216     // If the message interface is a subclass of the original interface, accept
 217     // the message unless there is a subclass in the hierarchy that will
 218     // "steal" the message (thus the message "will go" to the subclass and not
 219     /// the original interface).
 220     if (IFace) {
 221       Selector Sel = Msg->getSelector();
 222       for (ObjCInterfaceDecl *Cls = MsgD; Cls; Cls = Cls->getSuperClass()) {
 223         if (Cls == IFace)
 224           return true;
 225         if (Cls->getMethod(Sel, IsInstanceMethod))
 226           return false;
 227       }
 228     }
 229
 230     // The interfaces are unrelated, don't accept the message.
 231     return false;
 232   }
 233 };
 234
 235 //===----------------------------------------------------------------------===//
 236 // MessageAnalyzer Implementation
 237 //===----------------------------------------------------------------------===//
 238
 239 /// \brief Accepts an ObjC message expression and finds all methods that may
 240 /// respond to it.
 241 class MessageAnalyzer : public TranslationUnitHandler {
 242   Program &Prog;
 243   TULocationHandler &TULocHandler;
 244
 245   // The ObjCInterface associated with the message. Can be null/invalid.
 246   Entity MsgIFaceEnt;
 247   GlobalSelector GlobSel;
 248   bool CanBeInstanceMethod;
 249   bool CanBeClassMethod;
 250
 251   /// \brief Super classes of the ObjCInterface.
 252   typedef llvm::SmallSet<Entity, 16> EntitiesSetTy;
 253   EntitiesSetTy HierarchyEntities;
 254
 255   /// \brief The interface in the message interface hierarchy that "intercepts"
 256   /// the selector.
 257   Entity ReceiverIFaceEnt;
 258
 259 public:
 260   MessageAnalyzer(ObjCMessageExpr *Msg,
 261                   Program &prog, TULocationHandler &handler)
 262     : Prog(prog), TULocHandler(handler),
 263       CanBeInstanceMethod(false),
 264       CanBeClassMethod(false) {
 265
 266     assert(Msg);
 267
 268     ObjCInterfaceDecl *MsgD = 0;
 269
 270     while (true) {
 271       switch (Msg->getReceiverKind()) {
 272       case ObjCMessageExpr::Instance: {
 273         const ObjCObjectPointerType *OPT =
 274           Msg->getInstanceReceiver()->getType()
 275                                       ->getAsObjCInterfacePointerType();
 276
 277         if (!OPT || OPT->isObjCIdType() || OPT->isObjCQualifiedIdType()) {
 278           CanBeInstanceMethod = CanBeClassMethod = true;
 279           break;
 280         }
 281
 282         if (OPT->isObjCClassType() || OPT->isObjCQualifiedClassType()) {
 283           CanBeClassMethod = true;
 284           break;
 285         }
 286
 287         MsgD = OPT->getInterfaceDecl();
 288         assert(MsgD);
 289         CanBeInstanceMethod = true;
 290         break;
 291       }
 292
 293       case ObjCMessageExpr::Class:
 294         CanBeClassMethod = true;
 295         MsgD = Msg->getClassReceiver()->getAs<ObjCObjectType>()->getInterface();
 296         break;
 297
 298       case ObjCMessageExpr::SuperClass:
 299         CanBeClassMethod = true;
 300         MsgD = Msg->getSuperType()->getAs<ObjCObjectType>()->getInterface();
 301         break;
 302
 303       case ObjCMessageExpr::SuperInstance:
 304         CanBeInstanceMethod = true;
 305         MsgD = Msg->getSuperType()->getAs<ObjCObjectPointerType>()
 306                                                            ->getInterfaceDecl();
 307         break;
 308       }
 309     }
 310
 311     assert(CanBeInstanceMethod || CanBeClassMethod);
 312
 313     Selector sel = Msg->getSelector();
 314     assert(!sel.isNull());
 315
 316     MsgIFaceEnt = Entity::get(MsgD, Prog);
 317     GlobSel = GlobalSelector::get(sel, Prog);
 318
 319     if (MsgD) {
 320       for (ObjCInterfaceDecl *Cls = MsgD->getSuperClass();
 321              Cls; Cls = Cls->getSuperClass())
 322         HierarchyEntities.insert(Entity::get(Cls, Prog));
 323
 324       // Find the interface in the hierarchy that "receives" the message.
 325       for (ObjCInterfaceDecl *Cls = MsgD; Cls; Cls = Cls->getSuperClass()) {
 326         bool isReceiver = false;
 327
 328         ObjCInterfaceDecl::lookup_const_iterator Meth, MethEnd;
 329         for (llvm::tie(Meth, MethEnd) = Cls->lookup(sel);
 330                Meth != MethEnd; ++Meth) {
 331           if (ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(*Meth))
 332             if ((MD->isInstanceMethod() && CanBeInstanceMethod) ||
 333                 (MD->isClassMethod()    && CanBeClassMethod)) {
 334               isReceiver = true;
 335               break;
 336             }
 337         }
 338
 339         if (isReceiver) {
 340           ReceiverIFaceEnt = Entity::get(Cls, Prog);
 341           break;
 342         }
 343       }
 344     }
 345   }
 346
 347   virtual void Handle(TranslationUnit *TU) {
 348     assert(TU && "Passed null translation unit");
 349     ASTContext &Ctx = TU->getASTContext();
 350
 351     // Null means it doesn't exist in this translation unit or there was no
 352     // interface that was determined to receive the original message.
 353     ObjCInterfaceDecl *ReceiverIFace =
 354         cast_or_null<ObjCInterfaceDecl>(ReceiverIFaceEnt.getDecl(Ctx));
 355
 356     // No subclass for the original receiver interface, so it remains the
 357     // receiver.
 358     if (ReceiverIFaceEnt.isValid() && ReceiverIFace == 0)
 359       return;
 360
 361     // Null means it doesn't exist in this translation unit or there was no
 362     // interface associated with the message in the first place.
 363     ObjCInterfaceDecl *MsgIFace =
 364         cast_or_null<ObjCInterfaceDecl>(MsgIFaceEnt.getDecl(Ctx));
 365
 366     Selector Sel = GlobSel.getSelector(Ctx);
 367     SelectorMap &SelMap = TU->getSelectorMap();
 368     for (SelectorMap::method_iterator
 369            I = SelMap.methods_begin(Sel), E = SelMap.methods_end(Sel);
 370            I != E; ++I) {
 371       ObjCMethodDecl *D = *I;
 372       if (ValidMethod(D, MsgIFace, ReceiverIFace)) {
 373         for (ObjCMethodDecl::redecl_iterator
 374                RI = D->redecls_begin(), RE = D->redecls_end(); RI != RE; ++RI)
 375           TULocHandler.Handle(TULocation(TU, ASTLocation(*RI)));
 376       }
 377     }
 378   }
 379
 380   /// \brief Determines whether the given method is likely to accept the
 381   /// original message.
 382   ///
 383   /// It returns true "eagerly", meaning it will return false only if it can
 384   /// "prove" statically that the method cannot accept the original message.
 385   bool ValidMethod(ObjCMethodDecl *D, ObjCInterfaceDecl *MsgIFace,
 386                    ObjCInterfaceDecl *ReceiverIFace) {
 387     assert(D);
 388
 389     // FIXME: Protocol methods ?
 390     if (isa<ObjCProtocolDecl>(D->getDeclContext()))
 391       return false;
 392
 393     // No specific interface associated with the message. Can be anything.
 394     if (MsgIFaceEnt.isInvalid())
 395       return true;
 396
 397     if ((!CanBeInstanceMethod && D->isInstanceMethod()) ||
 398         (!CanBeClassMethod    && D->isClassMethod()))
 399       return false;
 400
 401     ObjCInterfaceDecl *IFace = D->getClassInterface();
 402     assert(IFace);
 403
 404     // If the original message interface is the same or a superclass of the
 405     // given interface, accept the method as a possibility.
 406     if (MsgIFace && MsgIFace->isSuperClassOf(IFace))
 407       return true;
 408
 409     if (ReceiverIFace) {
 410       // The given interface, "overrides" the receiver.
 411       if (ReceiverIFace->isSuperClassOf(IFace))
 412         return true;
 413     } else {
 414       // No receiver was found for the original message.
 415       assert(ReceiverIFaceEnt.isInvalid());
 416
 417       // If the original message interface is a subclass of the given interface,
 418       // accept the message.
 419       if (HierarchyEntities.count(Entity::get(IFace, Prog)))
 420         return true;
 421     }
 422
 423     // The interfaces are unrelated, or the receiver interface wasn't
 424     // "overriden".
 425     return false;
 426   }
 427 };
 428
 429 } // end anonymous namespace
 430
 431 //===----------------------------------------------------------------------===//
 432 // Analyzer Implementation
 433 //===----------------------------------------------------------------------===//
 434
 435 void Analyzer::FindDeclarations(Decl *D, TULocationHandler &Handler) {
 436   assert(D && "Passed null declaration");
 437   Entity Ent = Entity::get(D, Prog);
 438   if (Ent.isInvalid())
 439     return;
 440
 441   DeclEntityAnalyzer DEA(Ent, Handler);
 442   Idxer.GetTranslationUnitsFor(Ent, DEA);
 443 }
 444
 445 void Analyzer::FindReferences(Decl *D, TULocationHandler &Handler) {
 446   assert(D && "Passed null declaration");
 447   if (ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
 448     RefSelectorAnalyzer RSA(MD, Prog, Handler);
 449     GlobalSelector Sel = GlobalSelector::get(MD->getSelector(), Prog);
 450     Idxer.GetTranslationUnitsFor(Sel, RSA);
 451     return;
 452   }
 453
 454   Entity Ent = Entity::get(D, Prog);
 455   if (Ent.isInvalid())
 456     return;
 457
 458   RefEntityAnalyzer REA(Ent, Handler);
 459   Idxer.GetTranslationUnitsFor(Ent, REA);
 460 }
 461
 462 /// \brief Find methods that may respond to the given message and pass them
 463 /// to Handler.
 464 void Analyzer::FindObjCMethods(ObjCMessageExpr *Msg,
 465                                TULocationHandler &Handler) {
 466   assert(Msg);
 467   MessageAnalyzer MsgAnalyz(Msg, Prog, Handler);
 468   GlobalSelector GlobSel = GlobalSelector::get(Msg->getSelector(), Prog);
 469   Idxer.GetTranslationUnitsFor(GlobSel, MsgAnalyz);
 470 }