contrib/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h

   1 //===- CallEvent.h - Wrapper for all function and method calls ----*- 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 /// \file This file defines CallEvent and its subclasses, which represent path-
  11 /// sensitive instances of different kinds of function and method calls
  12 /// (C, C++, and Objective-C).
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CALLEVENT_H
  17 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CALLEVENT_H
  18
  19 #include "clang/AST/DeclCXX.h"
  20 #include "clang/AST/ExprCXX.h"
  21 #include "clang/AST/ExprObjC.h"
  22 #include "clang/Analysis/AnalysisContext.h"
  23 #include "clang/Basic/SourceManager.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  25 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  26 #include "llvm/ADT/PointerIntPair.h"
  27 #include <utility>
  28
  29 namespace clang {
  30 class ProgramPoint;
  31 class ProgramPointTag;
  32
  33 namespace ento {
  34
  35 enum CallEventKind {
  36   CE_Function,
  37   CE_CXXMember,
  38   CE_CXXMemberOperator,
  39   CE_CXXDestructor,
  40   CE_BEG_CXX_INSTANCE_CALLS = CE_CXXMember,
  41   CE_END_CXX_INSTANCE_CALLS = CE_CXXDestructor,
  42   CE_CXXConstructor,
  43   CE_CXXAllocator,
  44   CE_BEG_FUNCTION_CALLS = CE_Function,
  45   CE_END_FUNCTION_CALLS = CE_CXXAllocator,
  46   CE_Block,
  47   CE_ObjCMessage
  48 };
  49
  50 class CallEvent;
  51 class CallEventManager;
  52
  53 /// This class represents a description of a function call using the number of
  54 /// arguments and the name of the function.
  55 class CallDescription {
  56   friend CallEvent;
  57   mutable IdentifierInfo *II;
  58   mutable bool IsLookupDone;
  59   StringRef FuncName;
  60   unsigned RequiredArgs;
  61
  62 public:
  63   const static unsigned NoArgRequirement = ~0;
  64   /// \brief Constructs a CallDescription object.
  65   ///
  66   /// @param FuncName The name of the function that will be matched.
  67   ///
  68   /// @param RequiredArgs The number of arguments that is expected to match a
  69   /// call. Omit this parameter to match every occurance of call with a given
  70   /// name regardless the number of arguments.
  71   CallDescription(StringRef FuncName, unsigned RequiredArgs = NoArgRequirement)
  72       : II(nullptr), IsLookupDone(false), FuncName(FuncName),
  73         RequiredArgs(RequiredArgs) {}
  74
  75   /// \brief Get the name of the function that this object matches.
  76   StringRef getFunctionName() const { return FuncName; }
  77 };
  78
  79 template<typename T = CallEvent>
  80 class CallEventRef : public IntrusiveRefCntPtr<const T> {
  81 public:
  82   CallEventRef(const T *Call) : IntrusiveRefCntPtr<const T>(Call) {}
  83   CallEventRef(const CallEventRef &Orig) : IntrusiveRefCntPtr<const T>(Orig) {}
  84
  85   CallEventRef<T> cloneWithState(ProgramStateRef State) const {
  86     return this->get()->template cloneWithState<T>(State);
  87   }
  88
  89   // Allow implicit conversions to a superclass type, since CallEventRef
  90   // behaves like a pointer-to-const.
  91   template <typename SuperT>
  92   operator CallEventRef<SuperT> () const {
  93     return this->get();
  94   }
  95 };
  96
  97 /// \class RuntimeDefinition
  98 /// \brief Defines the runtime definition of the called function.
  99 ///
 100 /// Encapsulates the information we have about which Decl will be used
 101 /// when the call is executed on the given path. When dealing with dynamic
 102 /// dispatch, the information is based on DynamicTypeInfo and might not be
 103 /// precise.
 104 class RuntimeDefinition {
 105   /// The Declaration of the function which could be called at runtime.
 106   /// NULL if not available.
 107   const Decl *D;
 108
 109   /// The region representing an object (ObjC/C++) on which the method is
 110   /// called. With dynamic dispatch, the method definition depends on the
 111   /// runtime type of this object. NULL when the DynamicTypeInfo is
 112   /// precise.
 113   const MemRegion *R;
 114
 115 public:
 116   RuntimeDefinition(): D(nullptr), R(nullptr) {}
 117   RuntimeDefinition(const Decl *InD): D(InD), R(nullptr) {}
 118   RuntimeDefinition(const Decl *InD, const MemRegion *InR): D(InD), R(InR) {}
 119   const Decl *getDecl() { return D; }
 120
 121   /// \brief Check if the definition we have is precise.
 122   /// If not, it is possible that the call dispatches to another definition at
 123   /// execution time.
 124   bool mayHaveOtherDefinitions() { return R != nullptr; }
 125
 126   /// When other definitions are possible, returns the region whose runtime type
 127   /// determines the method definition.
 128   const MemRegion *getDispatchRegion() { return R; }
 129 };
 130
 131 /// \brief Represents an abstract call to a function or method along a
 132 /// particular path.
 133 ///
 134 /// CallEvents are created through the factory methods of CallEventManager.
 135 ///
 136 /// CallEvents should always be cheap to create and destroy. In order for
 137 /// CallEventManager to be able to re-use CallEvent-sized memory blocks,
 138 /// subclasses of CallEvent may not add any data members to the base class.
 139 /// Use the "Data" and "Location" fields instead.
 140 class CallEvent {
 141 public:
 142   typedef CallEventKind Kind;
 143
 144 private:
 145   ProgramStateRef State;
 146   const LocationContext *LCtx;
 147   llvm::PointerUnion<const Expr *, const Decl *> Origin;
 148
 149   void operator=(const CallEvent &) = delete;
 150
 151 protected:
 152   // This is user data for subclasses.
 153   const void *Data;
 154
 155   // This is user data for subclasses.
 156   // This should come right before RefCount, so that the two fields can be
 157   // packed together on LP64 platforms.
 158   SourceLocation Location;
 159
 160 private:
 161   mutable unsigned RefCount;
 162
 163   template <typename T> friend struct llvm::IntrusiveRefCntPtrInfo;
 164   void Retain() const { ++RefCount; }
 165   void Release() const;
 166
 167 protected:
 168   friend class CallEventManager;
 169
 170   CallEvent(const Expr *E, ProgramStateRef state, const LocationContext *lctx)
 171       : State(std::move(state)), LCtx(lctx), Origin(E), RefCount(0) {}
 172
 173   CallEvent(const Decl *D, ProgramStateRef state, const LocationContext *lctx)
 174       : State(std::move(state)), LCtx(lctx), Origin(D), RefCount(0) {}
 175
 176   // DO NOT MAKE PUBLIC
 177   CallEvent(const CallEvent &Original)
 178     : State(Original.State), LCtx(Original.LCtx), Origin(Original.Origin),
 179       Data(Original.Data), Location(Original.Location), RefCount(0) {}
 180
 181   /// Copies this CallEvent, with vtable intact, into a new block of memory.
 182   virtual void cloneTo(void *Dest) const = 0;
 183
 184   /// \brief Get the value of arbitrary expressions at this point in the path.
 185   SVal getSVal(const Stmt *S) const {
 186     return getState()->getSVal(S, getLocationContext());
 187   }
 188
 189
 190   typedef SmallVectorImpl<SVal> ValueList;
 191
 192   /// \brief Used to specify non-argument regions that will be invalidated as a
 193   /// result of this call.
 194   virtual void getExtraInvalidatedValues(ValueList &Values,
 195                  RegionAndSymbolInvalidationTraits *ETraits) const {}
 196
 197 public:
 198   virtual ~CallEvent() {}
 199
 200   /// \brief Returns the kind of call this is.
 201   virtual Kind getKind() const = 0;
 202
 203   /// \brief Returns the declaration of the function or method that will be
 204   /// called. May be null.
 205   virtual const Decl *getDecl() const {
 206     return Origin.dyn_cast<const Decl *>();
 207   }
 208
 209   /// \brief The state in which the call is being evaluated.
 210   const ProgramStateRef &getState() const {
 211     return State;
 212   }
 213
 214   /// \brief The context in which the call is being evaluated.
 215   const LocationContext *getLocationContext() const {
 216     return LCtx;
 217   }
 218
 219   /// \brief Returns the definition of the function or method that will be
 220   /// called.
 221   virtual RuntimeDefinition getRuntimeDefinition() const = 0;
 222
 223   /// \brief Returns the expression whose value will be the result of this call.
 224   /// May be null.
 225   const Expr *getOriginExpr() const {
 226     return Origin.dyn_cast<const Expr *>();
 227   }
 228
 229   /// \brief Returns the number of arguments (explicit and implicit).
 230   ///
 231   /// Note that this may be greater than the number of parameters in the
 232   /// callee's declaration, and that it may include arguments not written in
 233   /// the source.
 234   virtual unsigned getNumArgs() const = 0;
 235
 236   /// \brief Returns true if the callee is known to be from a system header.
 237   bool isInSystemHeader() const {
 238     const Decl *D = getDecl();
 239     if (!D)
 240       return false;
 241
 242     SourceLocation Loc = D->getLocation();
 243     if (Loc.isValid()) {
 244       const SourceManager &SM =
 245         getState()->getStateManager().getContext().getSourceManager();
 246       return SM.isInSystemHeader(D->getLocation());
 247     }
 248
 249     // Special case for implicitly-declared global operator new/delete.
 250     // These should be considered system functions.
 251     if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
 252       return FD->isOverloadedOperator() && FD->isImplicit() && FD->isGlobal();
 253
 254     return false;
 255   }
 256
 257   /// \brief Returns true if the CallEvent is a call to a function that matches
 258   /// the CallDescription.
 259   ///
 260   /// Note that this function is not intended to be used to match Obj-C method
 261   /// calls.
 262   bool isCalled(const CallDescription &CD) const;
 263
 264   /// \brief Returns a source range for the entire call, suitable for
 265   /// outputting in diagnostics.
 266   virtual SourceRange getSourceRange() const {
 267     return getOriginExpr()->getSourceRange();
 268   }
 269
 270   /// \brief Returns the value of a given argument at the time of the call.
 271   virtual SVal getArgSVal(unsigned Index) const;
 272
 273   /// \brief Returns the expression associated with a given argument.
 274   /// May be null if this expression does not appear in the source.
 275   virtual const Expr *getArgExpr(unsigned Index) const { return nullptr; }
 276
 277   /// \brief Returns the source range for errors associated with this argument.
 278   ///
 279   /// May be invalid if the argument is not written in the source.
 280   virtual SourceRange getArgSourceRange(unsigned Index) const;
 281
 282   /// \brief Returns the result type, adjusted for references.
 283   QualType getResultType() const;
 284
 285   /// \brief Returns the return value of the call.
 286   ///
 287   /// This should only be called if the CallEvent was created using a state in
 288   /// which the return value has already been bound to the origin expression.
 289   SVal getReturnValue() const;
 290
 291   /// \brief Returns true if the type of any of the non-null arguments satisfies
 292   /// the condition.
 293   bool hasNonNullArgumentsWithType(bool (*Condition)(QualType)) const;
 294
 295   /// \brief Returns true if any of the arguments appear to represent callbacks.
 296   bool hasNonZeroCallbackArg() const;
 297
 298   /// \brief Returns true if any of the arguments is void*.
 299   bool hasVoidPointerToNonConstArg() const;
 300
 301   /// \brief Returns true if any of the arguments are known to escape to long-
 302   /// term storage, even if this method will not modify them.
 303   // NOTE: The exact semantics of this are still being defined!
 304   // We don't really want a list of hardcoded exceptions in the long run,
 305   // but we don't want duplicated lists of known APIs in the short term either.
 306   virtual bool argumentsMayEscape() const {
 307     return hasNonZeroCallbackArg();
 308   }
 309
 310   /// \brief Returns true if the callee is an externally-visible function in the
 311   /// top-level namespace, such as \c malloc.
 312   ///
 313   /// You can use this call to determine that a particular function really is
 314   /// a library function and not, say, a C++ member function with the same name.
 315   ///
 316   /// If a name is provided, the function must additionally match the given
 317   /// name.
 318   ///
 319   /// Note that this deliberately excludes C++ library functions in the \c std
 320   /// namespace, but will include C library functions accessed through the
 321   /// \c std namespace. This also does not check if the function is declared
 322   /// as 'extern "C"', or if it uses C++ name mangling.
 323   // FIXME: Add a helper for checking namespaces.
 324   // FIXME: Move this down to AnyFunctionCall once checkers have more
 325   // precise callbacks.
 326   bool isGlobalCFunction(StringRef SpecificName = StringRef()) const;
 327
 328   /// \brief Returns the name of the callee, if its name is a simple identifier.
 329   ///
 330   /// Note that this will fail for Objective-C methods, blocks, and C++
 331   /// overloaded operators. The former is named by a Selector rather than a
 332   /// simple identifier, and the latter two do not have names.
 333   // FIXME: Move this down to AnyFunctionCall once checkers have more
 334   // precise callbacks.
 335   const IdentifierInfo *getCalleeIdentifier() const {
 336     const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(getDecl());
 337     if (!ND)
 338       return nullptr;
 339     return ND->getIdentifier();
 340   }
 341
 342   /// \brief Returns an appropriate ProgramPoint for this call.
 343   ProgramPoint getProgramPoint(bool IsPreVisit = false,
 344                                const ProgramPointTag *Tag = nullptr) const;
 345
 346   /// \brief Returns a new state with all argument regions invalidated.
 347   ///
 348   /// This accepts an alternate state in case some processing has already
 349   /// occurred.
 350   ProgramStateRef invalidateRegions(unsigned BlockCount,
 351                                     ProgramStateRef Orig = nullptr) const;
 352
 353   typedef std::pair<Loc, SVal> FrameBindingTy;
 354   typedef SmallVectorImpl<FrameBindingTy> BindingsTy;
 355
 356   /// Populates the given SmallVector with the bindings in the callee's stack
 357   /// frame at the start of this call.
 358   virtual void getInitialStackFrameContents(const StackFrameContext *CalleeCtx,
 359                                             BindingsTy &Bindings) const = 0;
 360
 361   /// Returns a copy of this CallEvent, but using the given state.
 362   template <typename T>
 363   CallEventRef<T> cloneWithState(ProgramStateRef NewState) const;
 364
 365   /// Returns a copy of this CallEvent, but using the given state.
 366   CallEventRef<> cloneWithState(ProgramStateRef NewState) const {
 367     return cloneWithState<CallEvent>(NewState);
 368   }
 369
 370   /// \brief Returns true if this is a statement is a function or method call
 371   /// of some kind.
 372   static bool isCallStmt(const Stmt *S);
 373
 374   /// \brief Returns the result type of a function or method declaration.
 375   ///
 376   /// This will return a null QualType if the result type cannot be determined.
 377   static QualType getDeclaredResultType(const Decl *D);
 378
 379   /// \brief Returns true if the given decl is known to be variadic.
 380   ///
 381   /// \p D must not be null.
 382   static bool isVariadic(const Decl *D);
 383
 384   // Iterator access to formal parameters and their types.
 385 private:
 386   struct GetTypeFn {
 387     QualType operator()(ParmVarDecl *PD) const { return PD->getType(); }
 388   };
 389
 390 public:
 391   /// Return call's formal parameters.
 392   ///
 393   /// Remember that the number of formal parameters may not match the number
 394   /// of arguments for all calls. However, the first parameter will always
 395   /// correspond with the argument value returned by \c getArgSVal(0).
 396   virtual ArrayRef<ParmVarDecl*> parameters() const = 0;
 397
 398   typedef llvm::mapped_iterator<ArrayRef<ParmVarDecl*>::iterator, GetTypeFn>
 399     param_type_iterator;
 400
 401   /// Returns an iterator over the types of the call's formal parameters.
 402   ///
 403   /// This uses the callee decl found by default name lookup rather than the
 404   /// definition because it represents a public interface, and probably has
 405   /// more annotations.
 406   param_type_iterator param_type_begin() const {
 407     return llvm::map_iterator(parameters().begin(), GetTypeFn());
 408   }
 409   /// \sa param_type_begin()
 410   param_type_iterator param_type_end() const {
 411     return llvm::map_iterator(parameters().end(), GetTypeFn());
 412   }
 413
 414   // For debugging purposes only
 415   void dump(raw_ostream &Out) const;
 416   void dump() const;
 417 };
 418
 419
 420 /// \brief Represents a call to any sort of function that might have a
 421 /// FunctionDecl.
 422 class AnyFunctionCall : public CallEvent {
 423 protected:
 424   AnyFunctionCall(const Expr *E, ProgramStateRef St,
 425                   const LocationContext *LCtx)
 426     : CallEvent(E, St, LCtx) {}
 427   AnyFunctionCall(const Decl *D, ProgramStateRef St,
 428                   const LocationContext *LCtx)
 429     : CallEvent(D, St, LCtx) {}
 430   AnyFunctionCall(const AnyFunctionCall &Other) : CallEvent(Other) {}
 431
 432 public:
 433   // This function is overridden by subclasses, but they must return
 434   // a FunctionDecl.
 435   const FunctionDecl *getDecl() const override {
 436     return cast<FunctionDecl>(CallEvent::getDecl());
 437   }
 438
 439   RuntimeDefinition getRuntimeDefinition() const override {
 440     const FunctionDecl *FD = getDecl();
 441     // Note that the AnalysisDeclContext will have the FunctionDecl with
 442     // the definition (if one exists).
 443     if (FD) {
 444       AnalysisDeclContext *AD =
 445         getLocationContext()->getAnalysisDeclContext()->
 446         getManager()->getContext(FD);
 447       if (AD->getBody())
 448         return RuntimeDefinition(AD->getDecl());
 449     }
 450
 451     return RuntimeDefinition();
 452   }
 453
 454   bool argumentsMayEscape() const override;
 455
 456   void getInitialStackFrameContents(const StackFrameContext *CalleeCtx,
 457                                     BindingsTy &Bindings) const override;
 458
 459   ArrayRef<ParmVarDecl *> parameters() const override;
 460
 461   static bool classof(const CallEvent *CA) {
 462     return CA->getKind() >= CE_BEG_FUNCTION_CALLS &&
 463            CA->getKind() <= CE_END_FUNCTION_CALLS;
 464   }
 465 };
 466
 467 /// \brief Represents a C function or static C++ member function call.
 468 ///
 469 /// Example: \c fun()
 470 class SimpleFunctionCall : public AnyFunctionCall {
 471   friend class CallEventManager;
 472
 473 protected:
 474   SimpleFunctionCall(const CallExpr *CE, ProgramStateRef St,
 475                      const LocationContext *LCtx)
 476     : AnyFunctionCall(CE, St, LCtx) {}
 477   SimpleFunctionCall(const SimpleFunctionCall &Other)
 478     : AnyFunctionCall(Other) {}
 479   void cloneTo(void *Dest) const override {
 480     new (Dest) SimpleFunctionCall(*this);
 481   }
 482
 483 public:
 484   virtual const CallExpr *getOriginExpr() const {
 485     return cast<CallExpr>(AnyFunctionCall::getOriginExpr());
 486   }
 487
 488   const FunctionDecl *getDecl() const override;
 489
 490   unsigned getNumArgs() const override { return getOriginExpr()->getNumArgs(); }
 491
 492   const Expr *getArgExpr(unsigned Index) const override {
 493     return getOriginExpr()->getArg(Index);
 494   }
 495
 496   Kind getKind() const override { return CE_Function; }
 497
 498   static bool classof(const CallEvent *CA) {
 499     return CA->getKind() == CE_Function;
 500   }
 501 };
 502
 503 /// \brief Represents a call to a block.
 504 ///
 505 /// Example: <tt>^{ /* ... */ }()</tt>
 506 class BlockCall : public CallEvent {
 507   friend class CallEventManager;
 508
 509 protected:
 510   BlockCall(const CallExpr *CE, ProgramStateRef St,
 511             const LocationContext *LCtx)
 512     : CallEvent(CE, St, LCtx) {}
 513
 514   BlockCall(const BlockCall &Other) : CallEvent(Other) {}
 515   void cloneTo(void *Dest) const override { new (Dest) BlockCall(*this); }
 516
 517   void getExtraInvalidatedValues(ValueList &Values,
 518          RegionAndSymbolInvalidationTraits *ETraits) const override;
 519
 520 public:
 521   virtual const CallExpr *getOriginExpr() const {
 522     return cast<CallExpr>(CallEvent::getOriginExpr());
 523   }
 524
 525   unsigned getNumArgs() const override { return getOriginExpr()->getNumArgs(); }
 526
 527   const Expr *getArgExpr(unsigned Index) const override {
 528     return getOriginExpr()->getArg(Index);
 529   }
 530
 531   /// \brief Returns the region associated with this instance of the block.
 532   ///
 533   /// This may be NULL if the block's origin is unknown.
 534   const BlockDataRegion *getBlockRegion() const;
 535
 536   const BlockDecl *getDecl() const override {
 537     const BlockDataRegion *BR = getBlockRegion();
 538     if (!BR)
 539       return nullptr;
 540     return BR->getDecl();
 541   }
 542
 543   bool isConversionFromLambda() const {
 544     const BlockDecl *BD = getDecl();
 545     if (!BD)
 546       return false;
 547
 548     return BD->isConversionFromLambda();
 549   }
 550
 551   /// \brief For a block converted from a C++ lambda, returns the block
 552   /// VarRegion for the variable holding the captured C++ lambda record.
 553   const VarRegion *getRegionStoringCapturedLambda() const {
 554     assert(isConversionFromLambda());
 555     const BlockDataRegion *BR = getBlockRegion();
 556     assert(BR && "Block converted from lambda must have a block region");
 557
 558     auto I = BR->referenced_vars_begin();
 559     assert(I != BR->referenced_vars_end());
 560
 561     return I.getCapturedRegion();
 562   }
 563
 564   RuntimeDefinition getRuntimeDefinition() const override {
 565     if (!isConversionFromLambda())
 566       return RuntimeDefinition(getDecl());
 567
 568     // Clang converts lambdas to blocks with an implicit user-defined
 569     // conversion operator method on the lambda record that looks (roughly)
 570     // like:
 571     //
 572     // typedef R(^block_type)(P1, P2, ...);
 573     // operator block_type() const {
 574     //   auto Lambda = *this;
 575     //   return ^(P1 p1, P2 p2, ...){
 576     //     /* return Lambda(p1, p2, ...); */
 577     //   };
 578     // }
 579     //
 580     // Here R is the return type of the lambda and P1, P2, ... are
 581     // its parameter types. 'Lambda' is a fake VarDecl captured by the block
 582     // that is initialized to a copy of the lambda.
 583     //
 584     // Sema leaves the body of a lambda-converted block empty (it is
 585     // produced by CodeGen), so we can't analyze it directly. Instead, we skip
 586     // the block body and analyze the operator() method on the captured lambda.
 587     const VarDecl *LambdaVD = getRegionStoringCapturedLambda()->getDecl();
 588     const CXXRecordDecl *LambdaDecl = LambdaVD->getType()->getAsCXXRecordDecl();
 589     CXXMethodDecl* LambdaCallOperator = LambdaDecl->getLambdaCallOperator();
 590
 591     return RuntimeDefinition(LambdaCallOperator);
 592   }
 593
 594   bool argumentsMayEscape() const override {
 595     return true;
 596   }
 597
 598   void getInitialStackFrameContents(const StackFrameContext *CalleeCtx,
 599                                     BindingsTy &Bindings) const override;
 600
 601   ArrayRef<ParmVarDecl*> parameters() const override;
 602
 603   Kind getKind() const override { return CE_Block; }
 604
 605   static bool classof(const CallEvent *CA) {
 606     return CA->getKind() == CE_Block;
 607   }
 608 };
 609
 610 /// \brief Represents a non-static C++ member function call, no matter how
 611 /// it is written.
 612 class CXXInstanceCall : public AnyFunctionCall {
 613 protected:
 614   void getExtraInvalidatedValues(ValueList &Values,
 615          RegionAndSymbolInvalidationTraits *ETraits) const override;
 616
 617   CXXInstanceCall(const CallExpr *CE, ProgramStateRef St,
 618                   const LocationContext *LCtx)
 619     : AnyFunctionCall(CE, St, LCtx) {}
 620   CXXInstanceCall(const FunctionDecl *D, ProgramStateRef St,
 621                   const LocationContext *LCtx)
 622     : AnyFunctionCall(D, St, LCtx) {}
 623
 624
 625   CXXInstanceCall(const CXXInstanceCall &Other) : AnyFunctionCall(Other) {}
 626
 627 public:
 628   /// \brief Returns the expression representing the implicit 'this' object.
 629   virtual const Expr *getCXXThisExpr() const { return nullptr; }
 630
 631   /// \brief Returns the value of the implicit 'this' object.
 632   virtual SVal getCXXThisVal() const;
 633
 634   const FunctionDecl *getDecl() const override;
 635
 636   RuntimeDefinition getRuntimeDefinition() const override;
 637
 638   void getInitialStackFrameContents(const StackFrameContext *CalleeCtx,
 639                                     BindingsTy &Bindings) const override;
 640
 641   static bool classof(const CallEvent *CA) {
 642     return CA->getKind() >= CE_BEG_CXX_INSTANCE_CALLS &&
 643            CA->getKind() <= CE_END_CXX_INSTANCE_CALLS;
 644   }
 645 };
 646
 647 /// \brief Represents a non-static C++ member function call.
 648 ///
 649 /// Example: \c obj.fun()
 650 class CXXMemberCall : public CXXInstanceCall {
 651   friend class CallEventManager;
 652
 653 protected:
 654   CXXMemberCall(const CXXMemberCallExpr *CE, ProgramStateRef St,
 655                 const LocationContext *LCtx)
 656     : CXXInstanceCall(CE, St, LCtx) {}
 657
 658   CXXMemberCall(const CXXMemberCall &Other) : CXXInstanceCall(Other) {}
 659   void cloneTo(void *Dest) const override { new (Dest) CXXMemberCall(*this); }
 660
 661 public:
 662   virtual const CXXMemberCallExpr *getOriginExpr() const {
 663     return cast<CXXMemberCallExpr>(CXXInstanceCall::getOriginExpr());
 664   }
 665
 666   unsigned getNumArgs() const override {
 667     if (const CallExpr *CE = getOriginExpr())
 668       return CE->getNumArgs();
 669     return 0;
 670   }
 671
 672   const Expr *getArgExpr(unsigned Index) const override {
 673     return getOriginExpr()->getArg(Index);
 674   }
 675
 676   const Expr *getCXXThisExpr() const override;
 677
 678   RuntimeDefinition getRuntimeDefinition() const override;
 679
 680   Kind getKind() const override { return CE_CXXMember; }
 681
 682   static bool classof(const CallEvent *CA) {
 683     return CA->getKind() == CE_CXXMember;
 684   }
 685 };
 686
 687 /// \brief Represents a C++ overloaded operator call where the operator is
 688 /// implemented as a non-static member function.
 689 ///
 690 /// Example: <tt>iter + 1</tt>
 691 class CXXMemberOperatorCall : public CXXInstanceCall {
 692   friend class CallEventManager;
 693
 694 protected:
 695   CXXMemberOperatorCall(const CXXOperatorCallExpr *CE, ProgramStateRef St,
 696                         const LocationContext *LCtx)
 697     : CXXInstanceCall(CE, St, LCtx) {}
 698
 699   CXXMemberOperatorCall(const CXXMemberOperatorCall &Other)
 700     : CXXInstanceCall(Other) {}
 701   void cloneTo(void *Dest) const override {
 702     new (Dest) CXXMemberOperatorCall(*this);
 703   }
 704
 705 public:
 706   virtual const CXXOperatorCallExpr *getOriginExpr() const {
 707     return cast<CXXOperatorCallExpr>(CXXInstanceCall::getOriginExpr());
 708   }
 709
 710   unsigned getNumArgs() const override {
 711     return getOriginExpr()->getNumArgs() - 1;
 712   }
 713   const Expr *getArgExpr(unsigned Index) const override {
 714     return getOriginExpr()->getArg(Index + 1);
 715   }
 716
 717   const Expr *getCXXThisExpr() const override;
 718
 719   Kind getKind() const override { return CE_CXXMemberOperator; }
 720
 721   static bool classof(const CallEvent *CA) {
 722     return CA->getKind() == CE_CXXMemberOperator;
 723   }
 724 };
 725
 726 /// \brief Represents an implicit call to a C++ destructor.
 727 ///
 728 /// This can occur at the end of a scope (for automatic objects), at the end
 729 /// of a full-expression (for temporaries), or as part of a delete.
 730 class CXXDestructorCall : public CXXInstanceCall {
 731   friend class CallEventManager;
 732
 733 protected:
 734   typedef llvm::PointerIntPair<const MemRegion *, 1, bool> DtorDataTy;
 735
 736   /// Creates an implicit destructor.
 737   ///
 738   /// \param DD The destructor that will be called.
 739   /// \param Trigger The statement whose completion causes this destructor call.
 740   /// \param Target The object region to be destructed.
 741   /// \param St The path-sensitive state at this point in the program.
 742   /// \param LCtx The location context at this point in the program.
 743   CXXDestructorCall(const CXXDestructorDecl *DD, const Stmt *Trigger,
 744                     const MemRegion *Target, bool IsBaseDestructor,
 745                     ProgramStateRef St, const LocationContext *LCtx)
 746     : CXXInstanceCall(DD, St, LCtx) {
 747     Data = DtorDataTy(Target, IsBaseDestructor).getOpaqueValue();
 748     Location = Trigger->getLocEnd();
 749   }
 750
 751   CXXDestructorCall(const CXXDestructorCall &Other) : CXXInstanceCall(Other) {}
 752   void cloneTo(void *Dest) const override {new (Dest) CXXDestructorCall(*this);}
 753
 754 public:
 755   SourceRange getSourceRange() const override { return Location; }
 756   unsigned getNumArgs() const override { return 0; }
 757
 758   RuntimeDefinition getRuntimeDefinition() const override;
 759
 760   /// \brief Returns the value of the implicit 'this' object.
 761   SVal getCXXThisVal() const override;
 762
 763   /// Returns true if this is a call to a base class destructor.
 764   bool isBaseDestructor() const {
 765     return DtorDataTy::getFromOpaqueValue(Data).getInt();
 766   }
 767
 768   Kind getKind() const override { return CE_CXXDestructor; }
 769
 770   static bool classof(const CallEvent *CA) {
 771     return CA->getKind() == CE_CXXDestructor;
 772   }
 773 };
 774
 775 /// \brief Represents a call to a C++ constructor.
 776 ///
 777 /// Example: \c T(1)
 778 class CXXConstructorCall : public AnyFunctionCall {
 779   friend class CallEventManager;
 780
 781 protected:
 782   /// Creates a constructor call.
 783   ///
 784   /// \param CE The constructor expression as written in the source.
 785   /// \param Target The region where the object should be constructed. If NULL,
 786   ///               a new symbolic region will be used.
 787   /// \param St The path-sensitive state at this point in the program.
 788   /// \param LCtx The location context at this point in the program.
 789   CXXConstructorCall(const CXXConstructExpr *CE, const MemRegion *Target,
 790                      ProgramStateRef St, const LocationContext *LCtx)
 791     : AnyFunctionCall(CE, St, LCtx) {
 792     Data = Target;
 793   }
 794
 795   CXXConstructorCall(const CXXConstructorCall &Other) : AnyFunctionCall(Other){}
 796   void cloneTo(void *Dest) const override { new (Dest) CXXConstructorCall(*this); }
 797
 798   void getExtraInvalidatedValues(ValueList &Values,
 799          RegionAndSymbolInvalidationTraits *ETraits) const override;
 800
 801 public:
 802   virtual const CXXConstructExpr *getOriginExpr() const {
 803     return cast<CXXConstructExpr>(AnyFunctionCall::getOriginExpr());
 804   }
 805
 806   const CXXConstructorDecl *getDecl() const override {
 807     return getOriginExpr()->getConstructor();
 808   }
 809
 810   unsigned getNumArgs() const override { return getOriginExpr()->getNumArgs(); }
 811
 812   const Expr *getArgExpr(unsigned Index) const override {
 813     return getOriginExpr()->getArg(Index);
 814   }
 815
 816   /// \brief Returns the value of the implicit 'this' object.
 817   SVal getCXXThisVal() const;
 818
 819   void getInitialStackFrameContents(const StackFrameContext *CalleeCtx,
 820                                     BindingsTy &Bindings) const override;
 821
 822   Kind getKind() const override { return CE_CXXConstructor; }
 823
 824   static bool classof(const CallEvent *CA) {
 825     return CA->getKind() == CE_CXXConstructor;
 826   }
 827 };
 828
 829 /// \brief Represents the memory allocation call in a C++ new-expression.
 830 ///
 831 /// This is a call to "operator new".
 832 class CXXAllocatorCall : public AnyFunctionCall {
 833   friend class CallEventManager;
 834
 835 protected:
 836   CXXAllocatorCall(const CXXNewExpr *E, ProgramStateRef St,
 837                    const LocationContext *LCtx)
 838     : AnyFunctionCall(E, St, LCtx) {}
 839
 840   CXXAllocatorCall(const CXXAllocatorCall &Other) : AnyFunctionCall(Other) {}
 841   void cloneTo(void *Dest) const override { new (Dest) CXXAllocatorCall(*this); }
 842
 843 public:
 844   virtual const CXXNewExpr *getOriginExpr() const {
 845     return cast<CXXNewExpr>(AnyFunctionCall::getOriginExpr());
 846   }
 847
 848   const FunctionDecl *getDecl() const override {
 849     return getOriginExpr()->getOperatorNew();
 850   }
 851
 852   unsigned getNumArgs() const override {
 853     return getOriginExpr()->getNumPlacementArgs() + 1;
 854   }
 855
 856   const Expr *getArgExpr(unsigned Index) const override {
 857     // The first argument of an allocator call is the size of the allocation.
 858     if (Index == 0)
 859       return nullptr;
 860     return getOriginExpr()->getPlacementArg(Index - 1);
 861   }
 862
 863   Kind getKind() const override { return CE_CXXAllocator; }
 864
 865   static bool classof(const CallEvent *CE) {
 866     return CE->getKind() == CE_CXXAllocator;
 867   }
 868 };
 869
 870 /// \brief Represents the ways an Objective-C message send can occur.
 871 //
 872 // Note to maintainers: OCM_Message should always be last, since it does not
 873 // need to fit in the Data field's low bits.
 874 enum ObjCMessageKind {
 875   OCM_PropertyAccess,
 876   OCM_Subscript,
 877   OCM_Message
 878 };
 879
 880 /// \brief Represents any expression that calls an Objective-C method.
 881 ///
 882 /// This includes all of the kinds listed in ObjCMessageKind.
 883 class ObjCMethodCall : public CallEvent {
 884   friend class CallEventManager;
 885
 886   const PseudoObjectExpr *getContainingPseudoObjectExpr() const;
 887
 888 protected:
 889   ObjCMethodCall(const ObjCMessageExpr *Msg, ProgramStateRef St,
 890                  const LocationContext *LCtx)
 891     : CallEvent(Msg, St, LCtx) {
 892     Data = nullptr;
 893   }
 894
 895   ObjCMethodCall(const ObjCMethodCall &Other) : CallEvent(Other) {}
 896   void cloneTo(void *Dest) const override { new (Dest) ObjCMethodCall(*this); }
 897
 898   void getExtraInvalidatedValues(ValueList &Values,
 899          RegionAndSymbolInvalidationTraits *ETraits) const override;
 900
 901   /// Check if the selector may have multiple definitions (may have overrides).
 902   virtual bool canBeOverridenInSubclass(ObjCInterfaceDecl *IDecl,
 903                                         Selector Sel) const;
 904
 905 public:
 906   virtual const ObjCMessageExpr *getOriginExpr() const {
 907     return cast<ObjCMessageExpr>(CallEvent::getOriginExpr());
 908   }
 909   const ObjCMethodDecl *getDecl() const override {
 910     return getOriginExpr()->getMethodDecl();
 911   }
 912   unsigned getNumArgs() const override {
 913     return getOriginExpr()->getNumArgs();
 914   }
 915   const Expr *getArgExpr(unsigned Index) const override {
 916     return getOriginExpr()->getArg(Index);
 917   }
 918
 919   bool isInstanceMessage() const {
 920     return getOriginExpr()->isInstanceMessage();
 921   }
 922   ObjCMethodFamily getMethodFamily() const {
 923     return getOriginExpr()->getMethodFamily();
 924   }
 925   Selector getSelector() const {
 926     return getOriginExpr()->getSelector();
 927   }
 928
 929   SourceRange getSourceRange() const override;
 930
 931   /// \brief Returns the value of the receiver at the time of this call.
 932   SVal getReceiverSVal() const;
 933
 934   /// \brief Return the value of 'self' if available.
 935   SVal getSelfSVal() const;
 936
 937   /// \brief Get the interface for the receiver.
 938   ///
 939   /// This works whether this is an instance message or a class message.
 940   /// However, it currently just uses the static type of the receiver.
 941   const ObjCInterfaceDecl *getReceiverInterface() const {
 942     return getOriginExpr()->getReceiverInterface();
 943   }
 944
 945   /// \brief Checks if the receiver refers to 'self' or 'super'.
 946   bool isReceiverSelfOrSuper() const;
 947
 948   /// Returns how the message was written in the source (property access,
 949   /// subscript, or explicit message send).
 950   ObjCMessageKind getMessageKind() const;
 951
 952   /// Returns true if this property access or subscript is a setter (has the
 953   /// form of an assignment).
 954   bool isSetter() const {
 955     switch (getMessageKind()) {
 956     case OCM_Message:
 957       llvm_unreachable("This is not a pseudo-object access!");
 958     case OCM_PropertyAccess:
 959       return getNumArgs() > 0;
 960     case OCM_Subscript:
 961       return getNumArgs() > 1;
 962     }
 963     llvm_unreachable("Unknown message kind");
 964   }
 965
 966   // Returns the property accessed by this method, either explicitly via
 967   // property syntax or implicitly via a getter or setter method. Returns
 968   // nullptr if the call is not a prooperty access.
 969   const ObjCPropertyDecl *getAccessedProperty() const;
 970
 971   RuntimeDefinition getRuntimeDefinition() const override;
 972
 973   bool argumentsMayEscape() const override;
 974
 975   void getInitialStackFrameContents(const StackFrameContext *CalleeCtx,
 976                                     BindingsTy &Bindings) const override;
 977
 978   ArrayRef<ParmVarDecl*> parameters() const override;
 979
 980   Kind getKind() const override { return CE_ObjCMessage; }
 981
 982   static bool classof(const CallEvent *CA) {
 983     return CA->getKind() == CE_ObjCMessage;
 984   }
 985 };
 986
 987
 988 /// \brief Manages the lifetime of CallEvent objects.
 989 ///
 990 /// CallEventManager provides a way to create arbitrary CallEvents "on the
 991 /// stack" as if they were value objects by keeping a cache of CallEvent-sized
 992 /// memory blocks. The CallEvents created by CallEventManager are only valid
 993 /// for the lifetime of the OwnedCallEvent that holds them; right now these
 994 /// objects cannot be copied and ownership cannot be transferred.
 995 class CallEventManager {
 996   friend class CallEvent;
 997
 998   llvm::BumpPtrAllocator &Alloc;
 999   SmallVector<void *, 8> Cache;
1000   typedef SimpleFunctionCall CallEventTemplateTy;
1001
1002   void reclaim(const void *Memory) {
1003     Cache.push_back(const_cast<void *>(Memory));
1004   }
1005
1006   /// Returns memory that can be initialized as a CallEvent.
1007   void *allocate() {
1008     if (Cache.empty())
1009       return Alloc.Allocate<CallEventTemplateTy>();
1010     else
1011       return Cache.pop_back_val();
1012   }
1013
1014   template <typename T, typename Arg>
1015   T *create(Arg A, ProgramStateRef St, const LocationContext *LCtx) {
1016     static_assert(sizeof(T) == sizeof(CallEventTemplateTy),
1017                   "CallEvent subclasses are not all the same size");
1018     return new (allocate()) T(A, St, LCtx);
1019   }
1020
1021   template <typename T, typename Arg1, typename Arg2>
1022   T *create(Arg1 A1, Arg2 A2, ProgramStateRef St, const LocationContext *LCtx) {
1023     static_assert(sizeof(T) == sizeof(CallEventTemplateTy),
1024                   "CallEvent subclasses are not all the same size");
1025     return new (allocate()) T(A1, A2, St, LCtx);
1026   }
1027
1028   template <typename T, typename Arg1, typename Arg2, typename Arg3>
1029   T *create(Arg1 A1, Arg2 A2, Arg3 A3, ProgramStateRef St,
1030             const LocationContext *LCtx) {
1031     static_assert(sizeof(T) == sizeof(CallEventTemplateTy),
1032                   "CallEvent subclasses are not all the same size");
1033     return new (allocate()) T(A1, A2, A3, St, LCtx);
1034   }
1035
1036   template <typename T, typename Arg1, typename Arg2, typename Arg3,
1037             typename Arg4>
1038   T *create(Arg1 A1, Arg2 A2, Arg3 A3, Arg4 A4, ProgramStateRef St,
1039             const LocationContext *LCtx) {
1040     static_assert(sizeof(T) == sizeof(CallEventTemplateTy),
1041                   "CallEvent subclasses are not all the same size");
1042     return new (allocate()) T(A1, A2, A3, A4, St, LCtx);
1043   }
1044
1045 public:
1046   CallEventManager(llvm::BumpPtrAllocator &alloc) : Alloc(alloc) {}
1047
1048
1049   CallEventRef<>
1050   getCaller(const StackFrameContext *CalleeCtx, ProgramStateRef State);
1051
1052
1053   CallEventRef<>
1054   getSimpleCall(const CallExpr *E, ProgramStateRef State,
1055                 const LocationContext *LCtx);
1056
1057   CallEventRef<ObjCMethodCall>
1058   getObjCMethodCall(const ObjCMessageExpr *E, ProgramStateRef State,
1059                     const LocationContext *LCtx) {
1060     return create<ObjCMethodCall>(E, State, LCtx);
1061   }
1062
1063   CallEventRef<CXXConstructorCall>
1064   getCXXConstructorCall(const CXXConstructExpr *E, const MemRegion *Target,
1065                         ProgramStateRef State, const LocationContext *LCtx) {
1066     return create<CXXConstructorCall>(E, Target, State, LCtx);
1067   }
1068
1069   CallEventRef<CXXDestructorCall>
1070   getCXXDestructorCall(const CXXDestructorDecl *DD, const Stmt *Trigger,
1071                        const MemRegion *Target, bool IsBase,
1072                        ProgramStateRef State, const LocationContext *LCtx) {
1073     return create<CXXDestructorCall>(DD, Trigger, Target, IsBase, State, LCtx);
1074   }
1075
1076   CallEventRef<CXXAllocatorCall>
1077   getCXXAllocatorCall(const CXXNewExpr *E, ProgramStateRef State,
1078                       const LocationContext *LCtx) {
1079     return create<CXXAllocatorCall>(E, State, LCtx);
1080   }
1081 };
1082
1083
1084 template <typename T>
1085 CallEventRef<T> CallEvent::cloneWithState(ProgramStateRef NewState) const {
1086   assert(isa<T>(*this) && "Cloning to unrelated type");
1087   static_assert(sizeof(T) == sizeof(CallEvent),
1088                 "Subclasses may not add fields");
1089
1090   if (NewState == State)
1091     return cast<T>(this);
1092
1093   CallEventManager &Mgr = State->getStateManager().getCallEventManager();
1094   T *Copy = static_cast<T *>(Mgr.allocate());
1095   cloneTo(Copy);
1096   assert(Copy->getKind() == this->getKind() && "Bad copy");
1097
1098   Copy->State = NewState;
1099   return Copy;
1100 }
1101
1102 inline void CallEvent::Release() const {
1103   assert(RefCount > 0 && "Reference count is already zero.");
1104   --RefCount;
1105
1106   if (RefCount > 0)
1107     return;
1108
1109   CallEventManager &Mgr = State->getStateManager().getCallEventManager();
1110   Mgr.reclaim(this);
1111
1112   this->~CallEvent();
1113 }
1114
1115 } // end namespace ento
1116 } // end namespace clang
1117
1118 namespace llvm {
1119   // Support isa<>, cast<>, and dyn_cast<> for CallEventRef.
1120   template<class T> struct simplify_type< clang::ento::CallEventRef<T> > {
1121     typedef const T *SimpleType;
1122
1123     static SimpleType
1124     getSimplifiedValue(clang::ento::CallEventRef<T> Val) {
1125       return Val.get();
1126     }
1127   };
1128 }
1129
1130 #endif