1// Copyright 2011 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28// This is clang plugin used by gcmole tool. See README for more details.
29
30#include "clang/AST/AST.h"
31#include "clang/AST/ASTConsumer.h"
32#include "clang/AST/Mangle.h"
33#include "clang/AST/RecursiveASTVisitor.h"
34#include "clang/AST/StmtVisitor.h"
35#include "clang/Frontend/FrontendPluginRegistry.h"
36#include "clang/Frontend/CompilerInstance.h"
37#include "llvm/Support/raw_ostream.h"
38
39#include <bitset>
40#include <fstream>
41#include <iostream>
42#include <map>
43#include <set>
44#include <stack>
45
46namespace {
47
48typedef std::string MangledName;
49typedef std::set<MangledName> CalleesSet;
50
51static bool GetMangledName(clang::MangleContext* ctx,
52                           const clang::NamedDecl* decl,
53                           MangledName* result) {
54  if (!isa<clang::CXXConstructorDecl>(decl) &&
55      !isa<clang::CXXDestructorDecl>(decl)) {
56    llvm::SmallVector<char, 512> output;
57    llvm::raw_svector_ostream out(output);
58    ctx->mangleName(decl, out);
59    *result = out.str().str();
60    return true;
61  }
62
63  return false;
64}
65
66
67static bool InV8Namespace(const clang::NamedDecl* decl) {
68  return decl->getQualifiedNameAsString().compare(0, 4, "v8::") == 0;
69}
70
71
72class CalleesPrinter : public clang::RecursiveASTVisitor<CalleesPrinter> {
73 public:
74  explicit CalleesPrinter(clang::MangleContext* ctx) : ctx_(ctx) {
75  }
76
77  virtual bool VisitCallExpr(clang::CallExpr* expr) {
78    const clang::FunctionDecl* callee = expr->getDirectCallee();
79    if (callee != NULL) AnalyzeFunction(callee);
80    return true;
81  }
82
83  void AnalyzeFunction(const clang::FunctionDecl* f) {
84    MangledName name;
85    if (InV8Namespace(f) && GetMangledName(ctx_, f, &name)) {
86      AddCallee(name);
87
88      const clang::FunctionDecl* body = NULL;
89      if (f->hasBody(body) && !Analyzed(name)) {
90        EnterScope(name);
91        TraverseStmt(body->getBody());
92        LeaveScope();
93      }
94    }
95  }
96
97  typedef std::map<MangledName, CalleesSet* > Callgraph;
98
99  bool Analyzed(const MangledName& name) {
100    return callgraph_[name] != NULL;
101  }
102
103  void EnterScope(const MangledName& name) {
104    CalleesSet* callees = callgraph_[name];
105
106    if (callees == NULL) {
107      callgraph_[name] = callees = new CalleesSet();
108    }
109
110    scopes_.push(callees);
111  }
112
113  void LeaveScope() {
114    scopes_.pop();
115  }
116
117  void AddCallee(const MangledName& name) {
118    if (!scopes_.empty()) scopes_.top()->insert(name);
119  }
120
121  void PrintCallGraph() {
122    for (Callgraph::const_iterator i = callgraph_.begin(), e = callgraph_.end();
123         i != e;
124         ++i) {
125      std::cout << i->first << "\n";
126
127      CalleesSet* callees = i->second;
128      for (CalleesSet::const_iterator j = callees->begin(), e = callees->end();
129           j != e;
130           ++j) {
131        std::cout << "\t" << *j << "\n";
132      }
133    }
134  }
135
136 private:
137  clang::MangleContext* ctx_;
138
139  std::stack<CalleesSet* > scopes_;
140  Callgraph callgraph_;
141};
142
143class FunctionDeclarationFinder
144    : public clang::ASTConsumer,
145      public clang::RecursiveASTVisitor<FunctionDeclarationFinder> {
146 public:
147  explicit FunctionDeclarationFinder(clang::Diagnostic& d,
148                                     clang::SourceManager& sm)
149      : d_(d), sm_(sm) { }
150
151  virtual void HandleTranslationUnit(clang::ASTContext &ctx) {
152    mangle_context_ = clang::createItaniumMangleContext(ctx, d_);
153    callees_printer_ = new CalleesPrinter(mangle_context_);
154
155    TraverseDecl(ctx.getTranslationUnitDecl());
156
157    callees_printer_->PrintCallGraph();
158  }
159
160  virtual bool VisitFunctionDecl(clang::FunctionDecl* decl) {
161    callees_printer_->AnalyzeFunction(decl);
162    return true;
163  }
164
165 private:
166  clang::Diagnostic& d_;
167  clang::SourceManager& sm_;
168  clang::MangleContext* mangle_context_;
169
170  CalleesPrinter* callees_printer_;
171};
172
173
174static bool loaded = false;
175static CalleesSet gc_suspects;
176
177
178static void LoadGCSuspects() {
179  if (loaded) return;
180
181  std::ifstream fin("gcsuspects");
182  std::string s;
183
184  while (fin >> s) gc_suspects.insert(s);
185
186  loaded = true;
187}
188
189
190static bool KnownToCauseGC(clang::MangleContext* ctx,
191                           const clang::FunctionDecl* decl) {
192  LoadGCSuspects();
193
194  if (!InV8Namespace(decl)) return false;
195
196  MangledName name;
197  if (GetMangledName(ctx, decl, &name)) {
198    return gc_suspects.find(name) != gc_suspects.end();
199  }
200
201  return false;
202}
203
204
205static bool IsHandleType(const clang::DeclarationName& handleDeclName,
206                         const clang::QualType& qtype) {
207  const clang::Type* canonical_type =
208      qtype.getTypePtr()->getCanonicalTypeUnqualified().getTypePtr();
209
210  if (const clang::TemplateSpecializationType* type =
211          canonical_type->getAs<clang::TemplateSpecializationType>()) {
212    if (clang::TemplateDecl* decl =
213            type->getTemplateName().getAsTemplateDecl()) {
214      if (decl->getTemplatedDecl()->getDeclName() == handleDeclName) {
215        return true;
216      }
217    }
218  } else if (const clang::RecordType* type =
219                 canonical_type->getAs<clang::RecordType>()) {
220    if (const clang::ClassTemplateSpecializationDecl* t =
221        dyn_cast<clang::ClassTemplateSpecializationDecl>(type->getDecl())) {
222      if (t->getSpecializedTemplate()->getDeclName() == handleDeclName) {
223        return true;
224      }
225    }
226  }
227
228  return false;
229}
230
231
232class ExpressionClassifier :
233    public clang::RecursiveASTVisitor<ExpressionClassifier> {
234 public:
235  ExpressionClassifier(clang::DeclarationName handleDeclName,
236                       clang::MangleContext* ctx,
237                       clang::CXXRecordDecl* objectDecl)
238      : handleDeclName_(handleDeclName),
239        ctx_(ctx),
240        objectDecl_(objectDecl) {
241  }
242
243  bool IsBadExpression(clang::Expr* expr) {
244    has_derefs_ = has_gc_ = false;
245    TraverseStmt(expr);
246    return has_derefs_ && has_gc_;
247  }
248
249  bool IsBadCallSite(clang::Expr* expr) {
250    if (isa<clang::CallExpr>(expr)) {
251      clang::CallExpr* call = cast<clang::CallExpr>(expr);
252
253      MarkGCSuspectAsArgument(call);
254      MarkHandleDereferenceAsArgument(call);
255
256      return derefs_.any() &&
257          ((gc_.count() > 1) || (gc_.any() && (gc_ ^ derefs_).any()));
258    }
259    return false;
260  }
261
262  virtual bool VisitExpr(clang::Expr* expr) {
263    has_derefs_ = has_derefs_ || IsRawPointerType(expr);
264    return !has_gc_ || !has_derefs_;
265  }
266
267  virtual bool VisitCallExpr(clang::CallExpr* expr) {
268    has_gc_ = has_gc_ || CanCauseGC(expr);
269    return !has_gc_ || !has_derefs_;
270  }
271 private:
272  void MarkHandleDereferenceAsArgument(clang::CallExpr* call) {
273    derefs_.reset();
274
275    if (clang::CXXMemberCallExpr* memcall =
276            dyn_cast<clang::CXXMemberCallExpr>(call)) {
277      if (ManipulatesRawPointers(memcall->getImplicitObjectArgument())) {
278        derefs_.set(0);
279      }
280    }
281
282    for (unsigned arg = 0; arg < call->getNumArgs(); arg++) {
283      if (ManipulatesRawPointers(call->getArg(arg))) derefs_.set(arg + 1);
284    }
285  }
286
287  void MarkGCSuspectAsArgument(clang::CallExpr* call) {
288    gc_.reset();
289
290    clang::CXXMemberCallExpr* memcall =
291        dyn_cast_or_null<clang::CXXMemberCallExpr>(call);
292    if (memcall != NULL && CanCauseGC(memcall->getImplicitObjectArgument())) {
293      gc_.set(0);
294    }
295
296    for (unsigned arg = 0; arg < call->getNumArgs(); arg++) {
297      if (CanCauseGC(call->getArg(arg))) gc_.set(arg + 1);
298    }
299  }
300
301  const clang::TagType* ToTagType(const clang::Type* t) {
302    if (t == NULL) {
303      return NULL;
304    } else if (isa<clang::TagType>(t)) {
305      return cast<clang::TagType>(t);
306    } else if (isa<clang::SubstTemplateTypeParmType>(t)) {
307      return ToTagType(cast<clang::SubstTemplateTypeParmType>(t)->
308                           getReplacementType().getTypePtr());
309    } else {
310      return NULL;
311    }
312  }
313
314  bool IsRawPointerType(clang::Expr* expr) {
315    clang::QualType result = expr->getType();
316
317    const clang::PointerType* type =
318        dyn_cast_or_null<clang::PointerType>(expr->getType().getTypePtr());
319    if (type == NULL) return false;
320
321    const clang::TagType* pointee =
322        ToTagType(type->getPointeeType().getTypePtr());
323    if (pointee == NULL) return false;
324
325    clang::CXXRecordDecl* record =
326        dyn_cast_or_null<clang::CXXRecordDecl>(pointee->getDecl());
327    if (record == NULL) return false;
328
329    return InV8Namespace(record) &&
330        record->hasDefinition() &&
331        ((record == objectDecl_) || record->isDerivedFrom(objectDecl_));
332  }
333
334  bool IsHandleDereference(clang::Expr* expr) {
335    if (expr == NULL) {
336      return false;
337    } else if (isa<clang::UnaryOperator>(expr)) {
338      clang::UnaryOperator* unop = cast<clang::UnaryOperator>(expr);
339      return unop->getOpcode() == clang::UO_Deref &&
340          IsHandleType(handleDeclName_, unop->getSubExpr()->getType());
341    } else if (isa<clang::CXXOperatorCallExpr>(expr)) {
342      clang::CXXOperatorCallExpr* op = cast<clang::CXXOperatorCallExpr>(expr);
343      return (op->getOperator() == clang::OO_Star ||
344              op->getOperator() == clang::OO_Arrow) &&
345          IsHandleType(handleDeclName_, op->getArg(0)->getType());
346    } else {
347      return false;
348    }
349  }
350
351  bool CanCauseGC(clang::Expr* expr) {
352    if (expr == NULL) return false;
353
354    has_gc_ = false;
355    has_derefs_ = true;
356    TraverseStmt(expr);
357    return has_gc_;
358  }
359
360  bool ManipulatesRawPointers(clang::Expr* expr) {
361    if (expr == NULL) return false;
362
363    has_gc_ = true;
364    has_derefs_ = false;
365    TraverseStmt(expr);
366    return has_derefs_;
367  }
368
369  bool CanCauseGC(const clang::CallExpr* call) {
370    const clang::FunctionDecl* fn = call->getDirectCallee();
371    return (fn != NULL) && KnownToCauseGC(ctx_, fn);
372  }
373
374  // For generic expression classification.
375  bool has_derefs_;
376  bool has_gc_;
377
378  // For callsite classification.
379  static const int kMaxNumberOfArguments = 64;
380  std::bitset<kMaxNumberOfArguments> derefs_;
381  std::bitset<kMaxNumberOfArguments> gc_;
382
383  clang::DeclarationName handleDeclName_;
384  clang::MangleContext* ctx_;
385  clang::CXXRecordDecl* objectDecl_;
386};
387
388const std::string BAD_EXPRESSION_MSG("Possible problem with evaluation order.");
389
390class ExpressionsFinder : public clang::ASTConsumer,
391                          public clang::RecursiveASTVisitor<ExpressionsFinder> {
392 public:
393  explicit ExpressionsFinder(clang::Diagnostic& d, clang::SourceManager& sm)
394      : d_(d), sm_(sm) { }
395
396  struct Resolver {
397    explicit Resolver(clang::ASTContext& ctx)
398        : ctx_(ctx), decl_ctx_(ctx.getTranslationUnitDecl()) {
399    }
400
401    Resolver(clang::ASTContext& ctx, clang::DeclContext* decl_ctx)
402        : ctx_(ctx), decl_ctx_(decl_ctx) {
403    }
404
405    clang::DeclarationName ResolveName(const char* n) {
406      clang::IdentifierInfo* ident = &ctx_.Idents.get(n);
407      return ctx_.DeclarationNames.getIdentifier(ident);
408    }
409
410    Resolver ResolveNamespace(const char* n) {
411      return Resolver(ctx_, Resolve<clang::NamespaceDecl>(n));
412    }
413
414    template<typename T>
415    T* Resolve(const char* n) {
416      if (decl_ctx_ == NULL) return NULL;
417
418      clang::DeclContext::lookup_result result =
419          decl_ctx_->lookup(ResolveName(n));
420
421      for (clang::DeclContext::lookup_iterator i = result.first,
422               e = result.second;
423           i != e;
424           i++) {
425        if (isa<T>(*i)) return cast<T>(*i);
426      }
427
428      return NULL;
429    }
430
431   private:
432    clang::ASTContext& ctx_;
433    clang::DeclContext* decl_ctx_;
434  };
435
436  virtual void HandleTranslationUnit(clang::ASTContext &ctx) {
437    Resolver r(ctx);
438
439    clang::CXXRecordDecl* objectDecl =
440        r.ResolveNamespace("v8").ResolveNamespace("internal").
441            Resolve<clang::CXXRecordDecl>("Object");
442
443    if (objectDecl != NULL) {
444      expression_classifier_ =
445          new ExpressionClassifier(r.ResolveName("Handle"),
446                                   clang::createItaniumMangleContext(ctx, d_),
447                                   objectDecl);
448      TraverseDecl(ctx.getTranslationUnitDecl());
449    } else {
450      std::cerr << "Failed to resolve v8::internal::Object" << std::endl;
451    }
452  }
453
454  virtual bool VisitExpr(clang::Expr* expr) {
455    if ( expression_classifier_->IsBadCallSite(expr) ) {
456      d_.Report(clang::FullSourceLoc(expr->getExprLoc(), sm_),
457                d_.getCustomDiagID(clang::Diagnostic::Warning,
458                                   BAD_EXPRESSION_MSG));
459    }
460
461    return true;
462  }
463
464 private:
465  clang::Diagnostic& d_;
466  clang::SourceManager& sm_;
467
468  ExpressionClassifier* expression_classifier_;
469};
470
471
472template<typename ConsumerType>
473class Action : public clang::PluginASTAction {
474 protected:
475  clang::ASTConsumer *CreateASTConsumer(clang::CompilerInstance &CI,
476                                        llvm::StringRef InFile) {
477    return new ConsumerType(CI.getDiagnostics(), CI.getSourceManager());
478  }
479
480  bool ParseArgs(const clang::CompilerInstance &CI,
481                 const std::vector<std::string>& args) {
482    return true;
483  }
484
485  void PrintHelp(llvm::raw_ostream& ros) { }
486};
487
488
489}
490
491static clang::FrontendPluginRegistry::Add<Action<ExpressionsFinder> >
492FindProblems("find-problems", "Find possible problems with evaluations order.");
493
494static clang::FrontendPluginRegistry::Add<Action<FunctionDeclarationFinder> >
495DumpCallees("dump-callees", "Dump callees for each function.");
496