Global cycle detection analysis.

tools/clang/blink_gc_plugin/BlinkGCPlugin.cpp

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // This clang plugin checks various invariants of the Blink garbage
 // collection infrastructure.
 //
 // Errors are described at:
 // http://www.chromium.org/developers/blink-gc-plugin-errors
 
 #include "Config.h"
+#include "JsonWriter.h"
 #include "RecordInfo.h"
 
 #include "clang/AST/AST.h"
 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendPluginRegistry.h"
 
 using namespace clang;
 using std::string;
@@ skipping 81 matching lines @@
     "[blink-gc] Field %0 requiring finalization declared here:";
 
 const char kManualDispatchMethodNote[] =
     "[blink-gc] Manual dispatch %0 declared here:";
 
 const char kDerivesNonStackAllocated[] =
     "[blink-gc] Stack-allocated class %0 derives class %1"
     " which is not stack allocated.";
 
 struct BlinkGCPluginOptions {
-  BlinkGCPluginOptions() : enable_oilpan(false) {}
+  BlinkGCPluginOptions() : enable_oilpan(false), detect_cycles(false) {}
   bool enable_oilpan;
+  bool detect_cycles;
   std::set<std::string> ignored_classes;
   std::set<std::string> checked_namespaces;
   std::vector<std::string> ignored_directories;
 };
 
 typedef std::vector<CXXRecordDecl*> RecordVector;
 typedef std::vector<CXXMethodDecl*> MethodVector;
 
 // Test if a template specialization is an instantiation.
 static bool IsTemplateInstantiation(CXXRecordDecl* record) {
@@ skipping 353 matching lines @@
 };
 
 // Main class containing checks for various invariants of the Blink
 // garbage collection infrastructure.
 class BlinkGCPluginConsumer : public ASTConsumer {
  public:
   BlinkGCPluginConsumer(CompilerInstance& instance,
                         const BlinkGCPluginOptions& options)
       : instance_(instance),
         diagnostic_(instance.getDiagnostics()),
-        options_(options) {
+        options_(options),
+        json_(0) {
 
     // Only check structures in the blink, WebCore and WebKit namespaces.
     options_.checked_namespaces.insert("blink");
     options_.checked_namespaces.insert("WebCore");
     options_.checked_namespaces.insert("WebKit");
 
     // Ignore GC implementation files.
     options_.ignored_directories.push_back("/heap/");
 
     // Register warning/error messages.
@@ skipping 55 matching lines @@
     diag_overridden_non_virtual_trace_note_ = diagnostic_.getCustomDiagID(
         DiagnosticsEngine::Note, kOverriddenNonVirtualTraceNote);
     diag_manual_dispatch_method_note_ = diagnostic_.getCustomDiagID(
         DiagnosticsEngine::Note, kManualDispatchMethodNote);
   }
 
   virtual void HandleTranslationUnit(ASTContext& context) {
     CollectVisitor visitor;
     visitor.TraverseDecl(context.getTranslationUnitDecl());
 
+    if (options_.detect_cycles) {
+      string err;
+      // TODO: Make createDefaultOutputFile or a shorter createOutputFile work.
+      json_ = JsonWriter::from(instance_.createOutputFile(
+          "",                                      // OutputPath
+          err,                                     // Errors
+          true,                                    // Binary
+          true,                                    // RemoveFileOnSignal
+          instance_.getFrontendOpts().OutputFile,  // BaseInput
+          "graph.json",                            // Extension
+          false,                                   // UseTemporary
+          false,                                   // CreateMissingDirectories
+          0,                                       // ResultPathName
+          0));                                     // TempPathName
+      if (err.empty() && json_) {
+        json_->OpenList();
+      } else {
+        json_ = 0;
+        llvm::errs()
+            << "[blink-gc] "
+            << "Failed to create an output file for the object graph.\n";
+      }
+    }
+
     for (RecordVector::iterator it = visitor.record_decls().begin();
          it != visitor.record_decls().end();
          ++it) {
       CheckRecord(cache_.Lookup(*it));
     }
 
     for (MethodVector::iterator it = visitor.trace_decls().begin();
          it != visitor.trace_decls().end();
          ++it) {
       CheckTracingMethod(*it);
     }
+
+    if (json_) {
+      json_->CloseList();
+      delete json_;
+      json_ = 0;
+    }
   }
 
   // Main entry for checking a record declaration.
   void CheckRecord(RecordInfo* info) {
     if (IsIgnored(info))
       return;
 
     CXXRecordDecl* record = info->record();
 
     // TODO: what should we do to check unions?
@@ skipping 42 matching lines @@
     }
 
     if (info->IsGCDerived()) {
       CheckGCRootsVisitor visitor;
       if (visitor.ContainsGCRoots(info))
         ReportClassContainsGCRoots(info, &visitor.gc_roots());
 
       if (info->NeedsFinalization())
         CheckFinalization(info);
     }
+
+    DumpClass(info);
   }
 
   void CheckDispatch(RecordInfo* info) {
     bool finalized = info->IsGCFinalized();
     CXXMethodDecl* trace_dispatch = info->GetTraceDispatchMethod();
     CXXMethodDecl* finalize_dispatch = info->GetFinalizeDispatchMethod();
     if (!trace_dispatch && !finalize_dispatch)
       return;
 
     CXXRecordDecl* base = trace_dispatch ?
@@ skipping 150 matching lines @@
          it != parent->GetFields().end();
          ++it) {
       if (!it->second.IsProperlyTraced()) {
         // Discontinue once an untraced-field error is found.
         ReportFieldsRequireTracing(parent, trace);
         break;
       }
     }
   }
 
+  void DumpClass(RecordInfo* info) {
+    if (!json_) return;
+
+    json_->OpenObject();
+    json_->Write("name", info->record()->getQualifiedNameAsString());
+    json_->Write("loc", GetLocString(info->record()->getLocStart()));
+    json_->CloseObject();
+
+    class DumpEdgeVisitor : public RecursiveEdgeVisitor {
+     public:
+      DumpEdgeVisitor(JsonWriter* json) : json_(json) { }
+      void DumpEdge(RecordInfo* src,
+                    RecordInfo* dst,
+                    const string& lbl,
+                    const Edge::LivenessKind& kind,
+                    const string& loc) {
+        json_->OpenObject();
+        json_->Write("src", src->record()->getQualifiedNameAsString());
+        json_->Write("dst", dst->record()->getQualifiedNameAsString());
+        json_->Write("lbl", lbl);
+        json_->Write("kind", kind);
+        json_->Write("loc", loc);
+        json_->CloseObject();
+      }
+
+      void DumpField(RecordInfo* src, FieldPoint* point, const string& loc) {
+        src_ = src;
+        point_ = point;
+        loc_ = loc;
+        point_->edge()->Accept(this);
+      }
+
+      void AtValue(Value* e) {
+        // The liveness kind of a path from the point to this value
+        // is given by the innermost place that is non-strong.
+        Edge::LivenessKind kind = Edge::kStrong;
+        if (Config::IsIgnoreCycleAnnotated(point_->field())) {
+          kind = Edge::kWeak;
+        } else {
+          for (Context::iterator it = context().begin();
+               it != context().end();
+               ++it) {
+            Edge::LivenessKind pointer_kind = (*it)->Kind();
+            if (pointer_kind != Edge::kStrong) {
+              kind = pointer_kind;
+              break;
+            }
+          }
+        }
+        DumpEdge(src_,
+                 e->value(),
+                 point_->field()->getNameAsString(),
+                 kind,
+                 loc_);
+      }
+
+     private:
+      JsonWriter* json_;
+      RecordInfo* src_;
+      FieldPoint* point_;
+      string loc_;
+    };
+
+    DumpEdgeVisitor visitor(json_);
+
+    RecordInfo::Bases& bases = info->GetBases();
+    for (RecordInfo::Bases::iterator it = bases.begin();
+         it != bases.end();
+         ++it) {
+      visitor.DumpEdge(info,
+                       it->second.info(),
+                       "<super>",
+                       Edge::kStrong,
+                       GetLocString(it->second.spec().getLocStart()));
+    }
+
+    RecordInfo::Fields& fields = info->GetFields();
+    for (RecordInfo::Fields::iterator it = fields.begin();
+         it != fields.end();
+         ++it) {
+      visitor.DumpField(info,
+                        &it->second,
+                        GetLocString(it->second.field()->getLocStart()));
+    }
+  }
+
   // Adds either a warning or error, based on the current handling of -Werror.
   DiagnosticsEngine::Level getErrorLevel() {
     return diagnostic_.getWarningsAsErrors() ? DiagnosticsEngine::Error
                                              : DiagnosticsEngine::Warning;
   }
 
+  const string GetLocString(SourceLocation loc) {
+    const SourceManager& source_manager = instance_.getSourceManager();
+    PresumedLoc ploc = source_manager.getPresumedLoc(loc);
+    if (ploc.isInvalid())
+      return "";
+    string loc_str;
+    llvm::raw_string_ostream OS(loc_str);
+    OS << ploc.getFilename()
+       << ":" << ploc.getLine()
+       << ":" << ploc.getColumn();
+    return OS.str();
+  }
+
   bool IsIgnored(RecordInfo* record) {
     return !record ||
            !InCheckedNamespace(record) ||
            IsIgnoredClass(record) ||
            InIgnoredDirectory(record);
   }
 
   bool IsIgnoredClass(RecordInfo* info) {
     // Ignore any class prefixed by SameSizeAs. These are used in
     // Blink to verify class sizes and don't need checking.
@@ skipping 302 matching lines @@
   unsigned diag_user_declared_finalizer_note_;
   unsigned diag_base_requires_finalization_note_;
   unsigned diag_field_requires_finalization_note_;
   unsigned diag_overridden_non_virtual_trace_note_;
   unsigned diag_manual_dispatch_method_note_;
 
   CompilerInstance& instance_;
   DiagnosticsEngine& diagnostic_;
   BlinkGCPluginOptions options_;
   RecordCache cache_;
+  JsonWriter* json_;
 };
 
 class BlinkGCPluginAction : public PluginASTAction {
  public:
   BlinkGCPluginAction() {}
 
  protected:
   // Overridden from PluginASTAction:
   virtual ASTConsumer* CreateASTConsumer(CompilerInstance& instance,
                                          llvm::StringRef ref) {
     return new BlinkGCPluginConsumer(instance, options_);
   }
 
   virtual bool ParseArgs(const CompilerInstance& instance,
                          const std::vector<string>& args) {
     bool parsed = true;
 
     for (size_t i = 0; i < args.size() && parsed; ++i) {
       if (args[i] == "enable-oilpan") {
         options_.enable_oilpan = true;
+      } else if (args[i] == "detect-cycles") {
+        options_.detect_cycles = true;
       } else {
         parsed = false;
         llvm::errs() << "Unknown blink-gc-plugin argument: " << args[i] << "\n";
       }
     }
 
     return parsed;
   }
 
  private:
   BlinkGCPluginOptions options_;
 };
 
 }  // namespace
 
 static FrontendPluginRegistry::Add<BlinkGCPluginAction> X(
     "blink-gc-plugin",
     "Check Blink GC invariants");