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