contrib/llvm/tools/clang/lib/Analysis/BodyFarm.cpp

   1 //== BodyFarm.cpp  - Factory for conjuring up fake bodies ----------*- 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 // BodyFarm is a factory for creating faux implementations for functions/methods
  11 // for analysis purposes.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "BodyFarm.h"
  16 #include "clang/AST/ASTContext.h"
  17 #include "clang/AST/Decl.h"
  18 #include "clang/AST/Expr.h"
  19 #include "clang/AST/ExprObjC.h"
  20 #include "clang/Analysis/CodeInjector.h"
  21 #include "llvm/ADT/StringSwitch.h"
  22
  23 using namespace clang;
  24
  25 //===----------------------------------------------------------------------===//
  26 // Helper creation functions for constructing faux ASTs.
  27 //===----------------------------------------------------------------------===//
  28
  29 static bool isDispatchBlock(QualType Ty) {
  30   // Is it a block pointer?
  31   const BlockPointerType *BPT = Ty->getAs<BlockPointerType>();
  32   if (!BPT)
  33     return false;
  34
  35   // Check if the block pointer type takes no arguments and
  36   // returns void.
  37   const FunctionProtoType *FT =
  38   BPT->getPointeeType()->getAs<FunctionProtoType>();
  39   return FT && FT->getReturnType()->isVoidType() && FT->getNumParams() == 0;
  40 }
  41
  42 namespace {
  43 class ASTMaker {
  44 public:
  45   ASTMaker(ASTContext &C) : C(C) {}
  46
  47   /// Create a new BinaryOperator representing a simple assignment.
  48   BinaryOperator *makeAssignment(const Expr *LHS, const Expr *RHS, QualType Ty);
  49
  50   /// Create a new BinaryOperator representing a comparison.
  51   BinaryOperator *makeComparison(const Expr *LHS, const Expr *RHS,
  52                                  BinaryOperator::Opcode Op);
  53
  54   /// Create a new compound stmt using the provided statements.
  55   CompoundStmt *makeCompound(ArrayRef<Stmt*>);
  56
  57   /// Create a new DeclRefExpr for the referenced variable.
  58   DeclRefExpr *makeDeclRefExpr(const VarDecl *D);
  59
  60   /// Create a new UnaryOperator representing a dereference.
  61   UnaryOperator *makeDereference(const Expr *Arg, QualType Ty);
  62
  63   /// Create an implicit cast for an integer conversion.
  64   Expr *makeIntegralCast(const Expr *Arg, QualType Ty);
  65
  66   /// Create an implicit cast to a builtin boolean type.
  67   ImplicitCastExpr *makeIntegralCastToBoolean(const Expr *Arg);
  68
  69   // Create an implicit cast for lvalue-to-rvaluate conversions.
  70   ImplicitCastExpr *makeLvalueToRvalue(const Expr *Arg, QualType Ty);
  71
  72   /// Create an Objective-C bool literal.
  73   ObjCBoolLiteralExpr *makeObjCBool(bool Val);
  74
  75   /// Create an Objective-C ivar reference.
  76   ObjCIvarRefExpr *makeObjCIvarRef(const Expr *Base, const ObjCIvarDecl *IVar);
  77
  78   /// Create a Return statement.
  79   ReturnStmt *makeReturn(const Expr *RetVal);
  80
  81 private:
  82   ASTContext &C;
  83 };
  84 }
  85
  86 BinaryOperator *ASTMaker::makeAssignment(const Expr *LHS, const Expr *RHS,
  87                                          QualType Ty) {
  88  return new (C) BinaryOperator(const_cast<Expr*>(LHS), const_cast<Expr*>(RHS),
  89                                BO_Assign, Ty, VK_RValue,
  90                                OK_Ordinary, SourceLocation(), false);
  91 }
  92
  93 BinaryOperator *ASTMaker::makeComparison(const Expr *LHS, const Expr *RHS,
  94                                          BinaryOperator::Opcode Op) {
  95   assert(BinaryOperator::isLogicalOp(Op) ||
  96          BinaryOperator::isComparisonOp(Op));
  97   return new (C) BinaryOperator(const_cast<Expr*>(LHS),
  98                                 const_cast<Expr*>(RHS),
  99                                 Op,
 100                                 C.getLogicalOperationType(),
 101                                 VK_RValue,
 102                                 OK_Ordinary, SourceLocation(), false);
 103 }
 104
 105 CompoundStmt *ASTMaker::makeCompound(ArrayRef<Stmt *> Stmts) {
 106   return new (C) CompoundStmt(C, Stmts, SourceLocation(), SourceLocation());
 107 }
 108
 109 DeclRefExpr *ASTMaker::makeDeclRefExpr(const VarDecl *D) {
 110   DeclRefExpr *DR =
 111     DeclRefExpr::Create(/* Ctx = */ C,
 112                         /* QualifierLoc = */ NestedNameSpecifierLoc(),
 113                         /* TemplateKWLoc = */ SourceLocation(),
 114                         /* D = */ const_cast<VarDecl*>(D),
 115                         /* RefersToEnclosingVariableOrCapture = */ false,
 116                         /* NameLoc = */ SourceLocation(),
 117                         /* T = */ D->getType(),
 118                         /* VK = */ VK_LValue);
 119   return DR;
 120 }
 121
 122 UnaryOperator *ASTMaker::makeDereference(const Expr *Arg, QualType Ty) {
 123   return new (C) UnaryOperator(const_cast<Expr*>(Arg), UO_Deref, Ty,
 124                                VK_LValue, OK_Ordinary, SourceLocation());
 125 }
 126
 127 ImplicitCastExpr *ASTMaker::makeLvalueToRvalue(const Expr *Arg, QualType Ty) {
 128   return ImplicitCastExpr::Create(C, Ty, CK_LValueToRValue,
 129                                   const_cast<Expr*>(Arg), nullptr, VK_RValue);
 130 }
 131
 132 Expr *ASTMaker::makeIntegralCast(const Expr *Arg, QualType Ty) {
 133   if (Arg->getType() == Ty)
 134     return const_cast<Expr*>(Arg);
 135
 136   return ImplicitCastExpr::Create(C, Ty, CK_IntegralCast,
 137                                   const_cast<Expr*>(Arg), nullptr, VK_RValue);
 138 }
 139
 140 ImplicitCastExpr *ASTMaker::makeIntegralCastToBoolean(const Expr *Arg) {
 141   return ImplicitCastExpr::Create(C, C.BoolTy, CK_IntegralToBoolean,
 142                                   const_cast<Expr*>(Arg), nullptr, VK_RValue);
 143 }
 144
 145 ObjCBoolLiteralExpr *ASTMaker::makeObjCBool(bool Val) {
 146   QualType Ty = C.getBOOLDecl() ? C.getBOOLType() : C.ObjCBuiltinBoolTy;
 147   return new (C) ObjCBoolLiteralExpr(Val, Ty, SourceLocation());
 148 }
 149
 150 ObjCIvarRefExpr *ASTMaker::makeObjCIvarRef(const Expr *Base,
 151                                            const ObjCIvarDecl *IVar) {
 152   return new (C) ObjCIvarRefExpr(const_cast<ObjCIvarDecl*>(IVar),
 153                                  IVar->getType(), SourceLocation(),
 154                                  SourceLocation(), const_cast<Expr*>(Base),
 155                                  /*arrow=*/true, /*free=*/false);
 156 }
 157
 158
 159 ReturnStmt *ASTMaker::makeReturn(const Expr *RetVal) {
 160   return new (C) ReturnStmt(SourceLocation(), const_cast<Expr*>(RetVal),
 161                             nullptr);
 162 }
 163
 164 //===----------------------------------------------------------------------===//
 165 // Creation functions for faux ASTs.
 166 //===----------------------------------------------------------------------===//
 167
 168 typedef Stmt *(*FunctionFarmer)(ASTContext &C, const FunctionDecl *D);
 169
 170 /// Create a fake body for dispatch_once.
 171 static Stmt *create_dispatch_once(ASTContext &C, const FunctionDecl *D) {
 172   // Check if we have at least two parameters.
 173   if (D->param_size() != 2)
 174     return nullptr;
 175
 176   // Check if the first parameter is a pointer to integer type.
 177   const ParmVarDecl *Predicate = D->getParamDecl(0);
 178   QualType PredicateQPtrTy = Predicate->getType();
 179   const PointerType *PredicatePtrTy = PredicateQPtrTy->getAs<PointerType>();
 180   if (!PredicatePtrTy)
 181     return nullptr;
 182   QualType PredicateTy = PredicatePtrTy->getPointeeType();
 183   if (!PredicateTy->isIntegerType())
 184     return nullptr;
 185
 186   // Check if the second parameter is the proper block type.
 187   const ParmVarDecl *Block = D->getParamDecl(1);
 188   QualType Ty = Block->getType();
 189   if (!isDispatchBlock(Ty))
 190     return nullptr;
 191
 192   // Everything checks out.  Create a fakse body that checks the predicate,
 193   // sets it, and calls the block.  Basically, an AST dump of:
 194   //
 195   // void dispatch_once(dispatch_once_t *predicate, dispatch_block_t block) {
 196   //  if (!*predicate) {
 197   //    *predicate = 1;
 198   //    block();
 199   //  }
 200   // }
 201
 202   ASTMaker M(C);
 203
 204   // (1) Create the call.
 205   DeclRefExpr *DR = M.makeDeclRefExpr(Block);
 206   ImplicitCastExpr *ICE = M.makeLvalueToRvalue(DR, Ty);
 207   CallExpr *CE = new (C) CallExpr(C, ICE, None, C.VoidTy, VK_RValue,
 208                                   SourceLocation());
 209
 210   // (2) Create the assignment to the predicate.
 211   IntegerLiteral *IL =
 212     IntegerLiteral::Create(C, llvm::APInt(C.getTypeSize(C.IntTy), (uint64_t) 1),
 213                            C.IntTy, SourceLocation());
 214   BinaryOperator *B =
 215     M.makeAssignment(
 216        M.makeDereference(
 217           M.makeLvalueToRvalue(
 218             M.makeDeclRefExpr(Predicate), PredicateQPtrTy),
 219             PredicateTy),
 220        M.makeIntegralCast(IL, PredicateTy),
 221        PredicateTy);
 222
 223   // (3) Create the compound statement.
 224   Stmt *Stmts[] = { B, CE };
 225   CompoundStmt *CS = M.makeCompound(Stmts);
 226
 227   // (4) Create the 'if' condition.
 228   ImplicitCastExpr *LValToRval =
 229     M.makeLvalueToRvalue(
 230       M.makeDereference(
 231         M.makeLvalueToRvalue(
 232           M.makeDeclRefExpr(Predicate),
 233           PredicateQPtrTy),
 234         PredicateTy),
 235     PredicateTy);
 236
 237   UnaryOperator *UO = new (C) UnaryOperator(LValToRval, UO_LNot, C.IntTy,
 238                                            VK_RValue, OK_Ordinary,
 239                                            SourceLocation());
 240
 241   // (5) Create the 'if' statement.
 242   IfStmt *If = new (C) IfStmt(C, SourceLocation(), nullptr, UO, CS);
 243   return If;
 244 }
 245
 246 /// Create a fake body for dispatch_sync.
 247 static Stmt *create_dispatch_sync(ASTContext &C, const FunctionDecl *D) {
 248   // Check if we have at least two parameters.
 249   if (D->param_size() != 2)
 250     return nullptr;
 251
 252   // Check if the second parameter is a block.
 253   const ParmVarDecl *PV = D->getParamDecl(1);
 254   QualType Ty = PV->getType();
 255   if (!isDispatchBlock(Ty))
 256     return nullptr;
 257
 258   // Everything checks out.  Create a fake body that just calls the block.
 259   // This is basically just an AST dump of:
 260   //
 261   // void dispatch_sync(dispatch_queue_t queue, void (^block)(void)) {
 262   //   block();
 263   // }
 264   //
 265   ASTMaker M(C);
 266   DeclRefExpr *DR = M.makeDeclRefExpr(PV);
 267   ImplicitCastExpr *ICE = M.makeLvalueToRvalue(DR, Ty);
 268   CallExpr *CE = new (C) CallExpr(C, ICE, None, C.VoidTy, VK_RValue,
 269                                   SourceLocation());
 270   return CE;
 271 }
 272
 273 static Stmt *create_OSAtomicCompareAndSwap(ASTContext &C, const FunctionDecl *D)
 274 {
 275   // There are exactly 3 arguments.
 276   if (D->param_size() != 3)
 277     return nullptr;
 278
 279   // Signature:
 280   // _Bool OSAtomicCompareAndSwapPtr(void *__oldValue,
 281   //                                 void *__newValue,
 282   //                                 void * volatile *__theValue)
 283   // Generate body:
 284   //   if (oldValue == *theValue) {
 285   //    *theValue = newValue;
 286   //    return YES;
 287   //   }
 288   //   else return NO;
 289
 290   QualType ResultTy = D->getReturnType();
 291   bool isBoolean = ResultTy->isBooleanType();
 292   if (!isBoolean && !ResultTy->isIntegralType(C))
 293     return nullptr;
 294
 295   const ParmVarDecl *OldValue = D->getParamDecl(0);
 296   QualType OldValueTy = OldValue->getType();
 297
 298   const ParmVarDecl *NewValue = D->getParamDecl(1);
 299   QualType NewValueTy = NewValue->getType();
 300
 301   assert(OldValueTy == NewValueTy);
 302
 303   const ParmVarDecl *TheValue = D->getParamDecl(2);
 304   QualType TheValueTy = TheValue->getType();
 305   const PointerType *PT = TheValueTy->getAs<PointerType>();
 306   if (!PT)
 307     return nullptr;
 308   QualType PointeeTy = PT->getPointeeType();
 309
 310   ASTMaker M(C);
 311   // Construct the comparison.
 312   Expr *Comparison =
 313     M.makeComparison(
 314       M.makeLvalueToRvalue(M.makeDeclRefExpr(OldValue), OldValueTy),
 315       M.makeLvalueToRvalue(
 316         M.makeDereference(
 317           M.makeLvalueToRvalue(M.makeDeclRefExpr(TheValue), TheValueTy),
 318           PointeeTy),
 319         PointeeTy),
 320       BO_EQ);
 321
 322   // Construct the body of the IfStmt.
 323   Stmt *Stmts[2];
 324   Stmts[0] =
 325     M.makeAssignment(
 326       M.makeDereference(
 327         M.makeLvalueToRvalue(M.makeDeclRefExpr(TheValue), TheValueTy),
 328         PointeeTy),
 329       M.makeLvalueToRvalue(M.makeDeclRefExpr(NewValue), NewValueTy),
 330       NewValueTy);
 331
 332   Expr *BoolVal = M.makeObjCBool(true);
 333   Expr *RetVal = isBoolean ? M.makeIntegralCastToBoolean(BoolVal)
 334                            : M.makeIntegralCast(BoolVal, ResultTy);
 335   Stmts[1] = M.makeReturn(RetVal);
 336   CompoundStmt *Body = M.makeCompound(Stmts);
 337
 338   // Construct the else clause.
 339   BoolVal = M.makeObjCBool(false);
 340   RetVal = isBoolean ? M.makeIntegralCastToBoolean(BoolVal)
 341                      : M.makeIntegralCast(BoolVal, ResultTy);
 342   Stmt *Else = M.makeReturn(RetVal);
 343
 344   /// Construct the If.
 345   Stmt *If =
 346     new (C) IfStmt(C, SourceLocation(), nullptr, Comparison, Body,
 347                    SourceLocation(), Else);
 348
 349   return If;
 350 }
 351
 352 Stmt *BodyFarm::getBody(const FunctionDecl *D) {
 353   D = D->getCanonicalDecl();
 354
 355   Optional<Stmt *> &Val = Bodies[D];
 356   if (Val.hasValue())
 357     return Val.getValue();
 358
 359   Val = nullptr;
 360
 361   if (D->getIdentifier() == nullptr)
 362     return nullptr;
 363
 364   StringRef Name = D->getName();
 365   if (Name.empty())
 366     return nullptr;
 367
 368   FunctionFarmer FF;
 369
 370   if (Name.startswith("OSAtomicCompareAndSwap") ||
 371       Name.startswith("objc_atomicCompareAndSwap")) {
 372     FF = create_OSAtomicCompareAndSwap;
 373   }
 374   else {
 375     FF = llvm::StringSwitch<FunctionFarmer>(Name)
 376           .Case("dispatch_sync", create_dispatch_sync)
 377           .Case("dispatch_once", create_dispatch_once)
 378           .Default(nullptr);
 379   }
 380
 381   if (FF) { Val = FF(C, D); }
 382   else if (Injector) { Val = Injector->getBody(D); }
 383   return Val.getValue();
 384 }
 385
 386 static Stmt *createObjCPropertyGetter(ASTContext &Ctx,
 387                                       const ObjCPropertyDecl *Prop) {
 388   // First, find the backing ivar.
 389   const ObjCIvarDecl *IVar = Prop->getPropertyIvarDecl();
 390   if (!IVar)
 391     return nullptr;
 392
 393   // Ignore weak variables, which have special behavior.
 394   if (Prop->getPropertyAttributes() & ObjCPropertyDecl::OBJC_PR_weak)
 395     return nullptr;
 396
 397   // Look to see if Sema has synthesized a body for us. This happens in
 398   // Objective-C++ because the return value may be a C++ class type with a
 399   // non-trivial copy constructor. We can only do this if we can find the
 400   // @synthesize for this property, though (or if we know it's been auto-
 401   // synthesized).
 402   const ObjCImplementationDecl *ImplDecl =
 403     IVar->getContainingInterface()->getImplementation();
 404   if (ImplDecl) {
 405     for (const auto *I : ImplDecl->property_impls()) {
 406       if (I->getPropertyDecl() != Prop)
 407         continue;
 408
 409       if (I->getGetterCXXConstructor()) {
 410         ASTMaker M(Ctx);
 411         return M.makeReturn(I->getGetterCXXConstructor());
 412       }
 413     }
 414   }
 415
 416   // Sanity check that the property is the same type as the ivar, or a
 417   // reference to it, and that it is either an object pointer or trivially
 418   // copyable.
 419   if (!Ctx.hasSameUnqualifiedType(IVar->getType(),
 420                                   Prop->getType().getNonReferenceType()))
 421     return nullptr;
 422   if (!IVar->getType()->isObjCLifetimeType() &&
 423       !IVar->getType().isTriviallyCopyableType(Ctx))
 424     return nullptr;
 425
 426   // Generate our body:
 427   //   return self->_ivar;
 428   ASTMaker M(Ctx);
 429
 430   const VarDecl *selfVar = Prop->getGetterMethodDecl()->getSelfDecl();
 431
 432   Expr *loadedIVar =
 433     M.makeObjCIvarRef(
 434       M.makeLvalueToRvalue(
 435         M.makeDeclRefExpr(selfVar),
 436         selfVar->getType()),
 437       IVar);
 438
 439   if (!Prop->getType()->isReferenceType())
 440     loadedIVar = M.makeLvalueToRvalue(loadedIVar, IVar->getType());
 441
 442   return M.makeReturn(loadedIVar);
 443 }
 444
 445 Stmt *BodyFarm::getBody(const ObjCMethodDecl *D) {
 446   // We currently only know how to synthesize property accessors.
 447   if (!D->isPropertyAccessor())
 448     return nullptr;
 449
 450   D = D->getCanonicalDecl();
 451
 452   Optional<Stmt *> &Val = Bodies[D];
 453   if (Val.hasValue())
 454     return Val.getValue();
 455   Val = nullptr;
 456
 457   const ObjCPropertyDecl *Prop = D->findPropertyDecl();
 458   if (!Prop)
 459     return nullptr;
 460
 461   // For now, we only synthesize getters.
 462   if (D->param_size() != 0)
 463     return nullptr;
 464
 465   Val = createObjCPropertyGetter(C, Prop);
 466
 467   return Val.getValue();
 468 }
 469