1 //===--- AnalysisConsumer.cpp - ASTConsumer for running Analyses ----------===//
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 // "Meta" ASTConsumer for running different source analyses.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #define DEBUG_TYPE "AnalysisConsumer"
15 
16 #include "AnalysisConsumer.h"
17 #include "clang/AST/ASTConsumer.h"
18 #include "clang/AST/Decl.h"
19 #include "clang/AST/DeclCXX.h"
20 #include "clang/AST/DeclObjC.h"
21 #include "clang/AST/ParentMap.h"
22 #include "clang/AST/RecursiveASTVisitor.h"
23 #include "clang/Analysis/CFG.h"
24 #include "clang/Analysis/CallGraph.h"
25 #include "clang/StaticAnalyzer/Frontend/CheckerRegistration.h"
26 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
27 #include "clang/StaticAnalyzer/Checkers/LocalCheckers.h"
28 #include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
29 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
30 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
31 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
32 #include "clang/StaticAnalyzer/Core/PathDiagnosticConsumers.h"
33 
34 #include "clang/Basic/FileManager.h"
35 #include "clang/Basic/SourceManager.h"
36 #include "clang/Frontend/AnalyzerOptions.h"
37 #include "clang/Lex/Preprocessor.h"
38 #include "llvm/Support/raw_ostream.h"
39 #include "llvm/Support/Path.h"
40 #include "llvm/Support/Program.h"
41 #include "llvm/Support/Timer.h"
42 #include "llvm/ADT/DepthFirstIterator.h"
43 #include "llvm/ADT/OwningPtr.h"
44 #include "llvm/ADT/SmallPtrSet.h"
45 #include "llvm/ADT/Statistic.h"
46 
47 #include <queue>
48 
49 using namespace clang;
50 using namespace ento;
51 using llvm::SmallPtrSet;
52 
53 static ExplodedNode::Auditor* CreateUbiViz();
54 
55 STATISTIC(NumFunctionTopLevel, "The # of functions at top level.");
56 STATISTIC(NumFunctionsAnalyzed, "The # of functions analysed (as top level).");
57 STATISTIC(NumBlocksInAnalyzedFunctions,
58                      "The # of basic blocks in the analyzed functions.");
59 STATISTIC(PercentReachableBlocks, "The % of reachable basic blocks.");
60 
61 //===----------------------------------------------------------------------===//
62 // Special PathDiagnosticConsumers.
63 //===----------------------------------------------------------------------===//
64 
65 static PathDiagnosticConsumer*
66 createPlistHTMLDiagnosticConsumer(const std::string& prefix,
67                                 const Preprocessor &PP) {
68   PathDiagnosticConsumer *PD =
69     createHTMLDiagnosticConsumer(llvm::sys::path::parent_path(prefix), PP);
70   return createPlistDiagnosticConsumer(prefix, PP, PD);
71 }
72 
73 //===----------------------------------------------------------------------===//
74 // AnalysisConsumer declaration.
75 //===----------------------------------------------------------------------===//
76 
77 namespace {
78 
79 class AnalysisConsumer : public ASTConsumer,
80                          public RecursiveASTVisitor<AnalysisConsumer> {
81   enum AnalysisMode {
82     ANALYSIS_SYNTAX,
83     ANALYSIS_PATH,
84     ANALYSIS_ALL
85   };
86 
87   /// Mode of the analyzes while recursively visiting Decls.
88   AnalysisMode RecVisitorMode;
89   /// Bug Reporter to use while recursively visiting Decls.
90   BugReporter *RecVisitorBR;
91 
92 public:
93   ASTContext *Ctx;
94   const Preprocessor &PP;
95   const std::string OutDir;
96   AnalyzerOptions Opts;
97   ArrayRef<std::string> Plugins;
98 
99   /// \brief Stores the declarations from the local translation unit.
100   /// Note, we pre-compute the local declarations at parse time as an
101   /// optimization to make sure we do not deserialize everything from disk.
102   /// The local declaration to all declarations ratio might be very small when
103   /// working with a PCH file.
104   SetOfDecls LocalTUDecls;
105 
106   // PD is owned by AnalysisManager.
107   PathDiagnosticConsumer *PD;
108 
109   StoreManagerCreator CreateStoreMgr;
110   ConstraintManagerCreator CreateConstraintMgr;
111 
112   OwningPtr<CheckerManager> checkerMgr;
113   OwningPtr<AnalysisManager> Mgr;
114 
115   /// Time the analyzes time of each translation unit.
116   static llvm::Timer* TUTotalTimer;
117 
118   /// The information about analyzed functions shared throughout the
119   /// translation unit.
120   FunctionSummariesTy FunctionSummaries;
121 
122   AnalysisConsumer(const Preprocessor& pp,
123                    const std::string& outdir,
124                    const AnalyzerOptions& opts,
125                    ArrayRef<std::string> plugins)
126     : RecVisitorMode(ANALYSIS_ALL), RecVisitorBR(0),
127       Ctx(0), PP(pp), OutDir(outdir), Opts(opts), Plugins(plugins), PD(0) {
128     DigestAnalyzerOptions();
129     if (Opts.PrintStats) {
130       llvm::EnableStatistics();
131       TUTotalTimer = new llvm::Timer("Analyzer Total Time");
132     }
133   }
134 
135   ~AnalysisConsumer() {
136     if (Opts.PrintStats)
137       delete TUTotalTimer;
138   }
139 
140   void DigestAnalyzerOptions() {
141     // Create the PathDiagnosticConsumer.
142     if (!OutDir.empty()) {
143       switch (Opts.AnalysisDiagOpt) {
144       default:
145 #define ANALYSIS_DIAGNOSTICS(NAME, CMDFLAG, DESC, CREATEFN, AUTOCREATE) \
146         case PD_##NAME: PD = CREATEFN(OutDir, PP); break;
147 #include "clang/Frontend/Analyses.def"
148       }
149     } else if (Opts.AnalysisDiagOpt == PD_TEXT) {
150       // Create the text client even without a specified output file since
151       // it just uses diagnostic notes.
152       PD = createTextPathDiagnosticConsumer("", PP);
153     }
154 
155     // Create the analyzer component creators.
156     switch (Opts.AnalysisStoreOpt) {
157     default:
158       llvm_unreachable("Unknown store manager.");
159 #define ANALYSIS_STORE(NAME, CMDFLAG, DESC, CREATEFN)           \
160       case NAME##Model: CreateStoreMgr = CREATEFN; break;
161 #include "clang/Frontend/Analyses.def"
162     }
163 
164     switch (Opts.AnalysisConstraintsOpt) {
165     default:
166       llvm_unreachable("Unknown store manager.");
167 #define ANALYSIS_CONSTRAINTS(NAME, CMDFLAG, DESC, CREATEFN)     \
168       case NAME##Model: CreateConstraintMgr = CREATEFN; break;
169 #include "clang/Frontend/Analyses.def"
170     }
171   }
172 
173   void DisplayFunction(const Decl *D, AnalysisMode Mode) {
174     if (!Opts.AnalyzerDisplayProgress)
175       return;
176 
177     SourceManager &SM = Mgr->getASTContext().getSourceManager();
178     PresumedLoc Loc = SM.getPresumedLoc(D->getLocation());
179     if (Loc.isValid()) {
180       llvm::errs() << "ANALYZE";
181       switch (Mode) {
182         case ANALYSIS_SYNTAX: llvm::errs() << "(Syntax)"; break;
183         case ANALYSIS_PATH: llvm::errs() << "(Path Sensitive)"; break;
184         case ANALYSIS_ALL: break;
185       };
186       llvm::errs() << ": " << Loc.getFilename();
187       if (isa<FunctionDecl>(D) || isa<ObjCMethodDecl>(D)) {
188         const NamedDecl *ND = cast<NamedDecl>(D);
189         llvm::errs() << ' ' << *ND << '\n';
190       }
191       else if (isa<BlockDecl>(D)) {
192         llvm::errs() << ' ' << "block(line:" << Loc.getLine() << ",col:"
193                      << Loc.getColumn() << '\n';
194       }
195       else if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
196         Selector S = MD->getSelector();
197         llvm::errs() << ' ' << S.getAsString();
198       }
199     }
200   }
201 
202   virtual void Initialize(ASTContext &Context) {
203     Ctx = &Context;
204     checkerMgr.reset(createCheckerManager(Opts, PP.getLangOpts(), Plugins,
205                                           PP.getDiagnostics()));
206     Mgr.reset(new AnalysisManager(*Ctx, PP.getDiagnostics(),
207                                   PP.getLangOpts(), PD,
208                                   CreateStoreMgr, CreateConstraintMgr,
209                                   checkerMgr.get(),
210                                   Opts.MaxNodes, Opts.MaxLoop,
211                                   Opts.VisualizeEGDot, Opts.VisualizeEGUbi,
212                                   Opts.AnalysisPurgeOpt, Opts.EagerlyAssume,
213                                   Opts.TrimGraph,
214                                   Opts.UnoptimizedCFG, Opts.CFGAddImplicitDtors,
215                                   Opts.CFGAddInitializers,
216                                   Opts.EagerlyTrimEGraph,
217                                   Opts.IPAMode,
218                                   Opts.InlineMaxStackDepth,
219                                   Opts.InlineMaxFunctionSize,
220                                   Opts.InliningMode,
221                                   Opts.NoRetryExhausted));
222   }
223 
224   /// \brief Store the top level decls in the set to be processed later on.
225   /// (Doing this pre-processing avoids deserialization of data from PCH.)
226   virtual bool HandleTopLevelDecl(DeclGroupRef D);
227   virtual void HandleTopLevelDeclInObjCContainer(DeclGroupRef D);
228 
229   virtual void HandleTranslationUnit(ASTContext &C);
230 
231   /// \brief Build the call graph for all the top level decls of this TU and
232   /// use it to define the order in which the functions should be visited.
233   void HandleDeclsGallGraph();
234 
235   /// \brief Run analyzes(syntax or path sensitive) on the given function.
236   /// \param Mode - determines if we are requesting syntax only or path
237   /// sensitive only analysis.
238   /// \param VisitedCallees - The output parameter, which is populated with the
239   /// set of functions which should be considered analyzed after analyzing the
240   /// given root function.
241   void HandleCode(Decl *D, AnalysisMode Mode,
242                   SetOfConstDecls *VisitedCallees = 0);
243 
244   void RunPathSensitiveChecks(Decl *D, SetOfConstDecls *VisitedCallees);
245   void ActionExprEngine(Decl *D, bool ObjCGCEnabled,
246                         SetOfConstDecls *VisitedCallees);
247 
248   /// Visitors for the RecursiveASTVisitor.
249 
250   /// Handle callbacks for arbitrary Decls.
251   bool VisitDecl(Decl *D) {
252     checkerMgr->runCheckersOnASTDecl(D, *Mgr, *RecVisitorBR);
253     return true;
254   }
255 
256   bool VisitFunctionDecl(FunctionDecl *FD) {
257     IdentifierInfo *II = FD->getIdentifier();
258     if (II && II->getName().startswith("__inline"))
259       return true;
260 
261     // We skip function template definitions, as their semantics is
262     // only determined when they are instantiated.
263     if (FD->isThisDeclarationADefinition() &&
264         !FD->isDependentContext()) {
265       HandleCode(FD, RecVisitorMode);
266     }
267     return true;
268   }
269 
270   bool VisitObjCMethodDecl(ObjCMethodDecl *MD) {
271     checkerMgr->runCheckersOnASTDecl(MD, *Mgr, *RecVisitorBR);
272     if (MD->isThisDeclarationADefinition())
273       HandleCode(MD, RecVisitorMode);
274     return true;
275   }
276 
277 private:
278   void storeTopLevelDecls(DeclGroupRef DG);
279 
280   /// \brief Check if we should skip (not analyze) the given function.
281   bool skipFunction(Decl *D);
282 
283 };
284 } // end anonymous namespace
285 
286 
287 //===----------------------------------------------------------------------===//
288 // AnalysisConsumer implementation.
289 //===----------------------------------------------------------------------===//
290 llvm::Timer* AnalysisConsumer::TUTotalTimer = 0;
291 
292 bool AnalysisConsumer::HandleTopLevelDecl(DeclGroupRef DG) {
293   storeTopLevelDecls(DG);
294   return true;
295 }
296 
297 void AnalysisConsumer::HandleTopLevelDeclInObjCContainer(DeclGroupRef DG) {
298   storeTopLevelDecls(DG);
299 }
300 
301 void AnalysisConsumer::storeTopLevelDecls(DeclGroupRef DG) {
302   for (DeclGroupRef::iterator I = DG.begin(), E = DG.end(); I != E; ++I) {
303 
304     // Skip ObjCMethodDecl, wait for the objc container to avoid
305     // analyzing twice.
306     if (isa<ObjCMethodDecl>(*I))
307       continue;
308 
309     LocalTUDecls.push_back(*I);
310   }
311 }
312 
313 void AnalysisConsumer::HandleDeclsGallGraph() {
314   // Otherwise, use the Callgraph to derive the order.
315   // Build the Call Graph.
316   CallGraph CG;
317   // Add all the top level declarations to the graph.
318   for (SetOfDecls::iterator I = LocalTUDecls.begin(),
319                             E = LocalTUDecls.end(); I != E; ++I)
320     CG.addToCallGraph(*I);
321 
322   // Find the top level nodes - children of root + the unreachable (parentless)
323   // nodes.
324   llvm::SmallVector<CallGraphNode*, 24> TopLevelFunctions;
325   for (CallGraph::nodes_iterator TI = CG.parentless_begin(),
326                                  TE = CG.parentless_end(); TI != TE; ++TI) {
327     TopLevelFunctions.push_back(*TI);
328     NumFunctionTopLevel++;
329   }
330   CallGraphNode *Entry = CG.getRoot();
331   for (CallGraphNode::iterator I = Entry->begin(),
332                                E = Entry->end(); I != E; ++I) {
333     TopLevelFunctions.push_back(*I);
334     NumFunctionTopLevel++;
335   }
336 
337   // Make sure the nodes are sorted in order reverse of their definition in the
338   // translation unit. This step is very important for performance. It ensures
339   // that we analyze the root functions before the externally available
340   // subroutines.
341   std::deque<CallGraphNode*> BFSQueue;
342   for (llvm::SmallVector<CallGraphNode*, 24>::reverse_iterator
343          TI = TopLevelFunctions.rbegin(), TE = TopLevelFunctions.rend();
344          TI != TE; ++TI)
345     BFSQueue.push_front(*TI);
346 
347   // BFS over all of the functions, while skipping the ones inlined into
348   // the previously processed functions. Use external Visited set, which is
349   // also modified when we inline a function.
350   SmallPtrSet<CallGraphNode*,24> Visited;
351   while(!BFSQueue.empty()) {
352     CallGraphNode *N = BFSQueue.front();
353     BFSQueue.pop_front();
354 
355     // Skip the functions which have been processed already or previously
356     // inlined.
357     if (Visited.count(N))
358       continue;
359 
360     // Analyze the function.
361     SetOfConstDecls VisitedCallees;
362     Decl *D = N->getDecl();
363     assert(D);
364     HandleCode(D, ANALYSIS_PATH,
365                (Mgr->InliningMode == All ? 0 : &VisitedCallees));
366 
367     // Add the visited callees to the global visited set.
368     for (SetOfConstDecls::iterator I = VisitedCallees.begin(),
369                                    E = VisitedCallees.end(); I != E; ++I) {
370       CallGraphNode *VN = CG.getNode(*I);
371       if (VN)
372         Visited.insert(VN);
373     }
374     Visited.insert(N);
375 
376     // Push the children into the queue.
377     for (CallGraphNode::const_iterator CI = N->begin(),
378                                        CE = N->end(); CI != CE; ++CI) {
379       BFSQueue.push_front(*CI);
380     }
381   }
382 }
383 
384 void AnalysisConsumer::HandleTranslationUnit(ASTContext &C) {
385   // Don't run the actions if an error has occurred with parsing the file.
386   DiagnosticsEngine &Diags = PP.getDiagnostics();
387   if (Diags.hasErrorOccurred() || Diags.hasFatalErrorOccurred())
388     return;
389 
390   {
391     if (TUTotalTimer) TUTotalTimer->startTimer();
392 
393     // Introduce a scope to destroy BR before Mgr.
394     BugReporter BR(*Mgr);
395     TranslationUnitDecl *TU = C.getTranslationUnitDecl();
396     checkerMgr->runCheckersOnASTDecl(TU, *Mgr, BR);
397 
398     // Run the AST-only checks using the order in which functions are defined.
399     // If inlining is not turned on, use the simplest function order for path
400     // sensitive analyzes as well.
401     RecVisitorMode = (Mgr->shouldInlineCall() ? ANALYSIS_SYNTAX : ANALYSIS_ALL);
402     RecVisitorBR = &BR;
403 
404     // Process all the top level declarations.
405     //
406     // Note: TraverseDecl may modify LocalTUDecls, but only by appending more
407     // entries.  Thus we don't use an iterator, but rely on LocalTUDecls
408     // random access.  By doing so, we automatically compensate for iterators
409     // possibly being invalidated, although this is a bit slower.
410     const unsigned n = LocalTUDecls.size();
411     for (unsigned i = 0 ; i < n ; ++i) {
412       TraverseDecl(LocalTUDecls[i]);
413     }
414 
415     if (Mgr->shouldInlineCall())
416       HandleDeclsGallGraph();
417 
418     // After all decls handled, run checkers on the entire TranslationUnit.
419     checkerMgr->runCheckersOnEndOfTranslationUnit(TU, *Mgr, BR);
420 
421     RecVisitorBR = 0;
422   }
423 
424   // Explicitly destroy the PathDiagnosticConsumer.  This will flush its output.
425   // FIXME: This should be replaced with something that doesn't rely on
426   // side-effects in PathDiagnosticConsumer's destructor. This is required when
427   // used with option -disable-free.
428   Mgr.reset(NULL);
429 
430   if (TUTotalTimer) TUTotalTimer->stopTimer();
431 
432   // Count how many basic blocks we have not covered.
433   NumBlocksInAnalyzedFunctions = FunctionSummaries.getTotalNumBasicBlocks();
434   if (NumBlocksInAnalyzedFunctions > 0)
435     PercentReachableBlocks =
436       (FunctionSummaries.getTotalNumVisitedBasicBlocks() * 100) /
437         NumBlocksInAnalyzedFunctions;
438 
439 }
440 
441 static void FindBlocks(DeclContext *D, SmallVectorImpl<Decl*> &WL) {
442   if (BlockDecl *BD = dyn_cast<BlockDecl>(D))
443     WL.push_back(BD);
444 
445   for (DeclContext::decl_iterator I = D->decls_begin(), E = D->decls_end();
446        I!=E; ++I)
447     if (DeclContext *DC = dyn_cast<DeclContext>(*I))
448       FindBlocks(DC, WL);
449 }
450 
451 static std::string getFunctionName(const Decl *D) {
452   if (const ObjCMethodDecl *ID = dyn_cast<ObjCMethodDecl>(D)) {
453     return ID->getSelector().getAsString();
454   }
455   if (const FunctionDecl *ND = dyn_cast<FunctionDecl>(D)) {
456     IdentifierInfo *II = ND->getIdentifier();
457     if (II)
458       return II->getName();
459   }
460   return "";
461 }
462 
463 bool AnalysisConsumer::skipFunction(Decl *D) {
464   if (!Opts.AnalyzeSpecificFunction.empty() &&
465       getFunctionName(D) != Opts.AnalyzeSpecificFunction)
466     return true;
467 
468   // Don't run the actions on declarations in header files unless
469   // otherwise specified.
470   SourceManager &SM = Ctx->getSourceManager();
471   SourceLocation SL = SM.getExpansionLoc(D->getLocation());
472   if (!Opts.AnalyzeAll && !SM.isFromMainFile(SL))
473     return true;
474 
475   return false;
476 }
477 
478 void AnalysisConsumer::HandleCode(Decl *D, AnalysisMode Mode,
479                                   SetOfConstDecls *VisitedCallees) {
480   if (skipFunction(D))
481     return;
482 
483   DisplayFunction(D, Mode);
484 
485   // Clear the AnalysisManager of old AnalysisDeclContexts.
486   Mgr->ClearContexts();
487 
488   // Dispatch on the actions.
489   SmallVector<Decl*, 10> WL;
490   WL.push_back(D);
491 
492   if (D->hasBody() && Opts.AnalyzeNestedBlocks)
493     FindBlocks(cast<DeclContext>(D), WL);
494 
495   BugReporter BR(*Mgr);
496   for (SmallVectorImpl<Decl*>::iterator WI=WL.begin(), WE=WL.end();
497        WI != WE; ++WI)
498     if ((*WI)->hasBody()) {
499       if (Mode != ANALYSIS_PATH)
500         checkerMgr->runCheckersOnASTBody(*WI, *Mgr, BR);
501       if (Mode != ANALYSIS_SYNTAX && checkerMgr->hasPathSensitiveCheckers()) {
502         RunPathSensitiveChecks(*WI, VisitedCallees);
503         NumFunctionsAnalyzed++;
504       }
505     }
506 }
507 
508 //===----------------------------------------------------------------------===//
509 // Path-sensitive checking.
510 //===----------------------------------------------------------------------===//
511 
512 void AnalysisConsumer::ActionExprEngine(Decl *D, bool ObjCGCEnabled,
513                                         SetOfConstDecls *VisitedCallees) {
514   // Construct the analysis engine.  First check if the CFG is valid.
515   // FIXME: Inter-procedural analysis will need to handle invalid CFGs.
516   if (!Mgr->getCFG(D))
517     return;
518 
519   ExprEngine Eng(*Mgr, ObjCGCEnabled, VisitedCallees, &FunctionSummaries);
520 
521   // Set the graph auditor.
522   OwningPtr<ExplodedNode::Auditor> Auditor;
523   if (Mgr->shouldVisualizeUbigraph()) {
524     Auditor.reset(CreateUbiViz());
525     ExplodedNode::SetAuditor(Auditor.get());
526   }
527 
528   // Execute the worklist algorithm.
529   Eng.ExecuteWorkList(Mgr->getAnalysisDeclContextManager().getStackFrame(D),
530                       Mgr->getMaxNodes());
531 
532   // Release the auditor (if any) so that it doesn't monitor the graph
533   // created BugReporter.
534   ExplodedNode::SetAuditor(0);
535 
536   // Visualize the exploded graph.
537   if (Mgr->shouldVisualizeGraphviz())
538     Eng.ViewGraph(Mgr->shouldTrimGraph());
539 
540   // Display warnings.
541   Eng.getBugReporter().FlushReports();
542 }
543 
544 void AnalysisConsumer::RunPathSensitiveChecks(Decl *D,
545                                               SetOfConstDecls *Visited) {
546 
547   switch (Mgr->getLangOpts().getGC()) {
548   case LangOptions::NonGC:
549     ActionExprEngine(D, false, Visited);
550     break;
551 
552   case LangOptions::GCOnly:
553     ActionExprEngine(D, true, Visited);
554     break;
555 
556   case LangOptions::HybridGC:
557     ActionExprEngine(D, false, Visited);
558     ActionExprEngine(D, true, Visited);
559     break;
560   }
561 }
562 
563 //===----------------------------------------------------------------------===//
564 // AnalysisConsumer creation.
565 //===----------------------------------------------------------------------===//
566 
567 ASTConsumer* ento::CreateAnalysisConsumer(const Preprocessor& pp,
568                                           const std::string& outDir,
569                                           const AnalyzerOptions& opts,
570                                           ArrayRef<std::string> plugins) {
571   // Disable the effects of '-Werror' when using the AnalysisConsumer.
572   pp.getDiagnostics().setWarningsAsErrors(false);
573 
574   return new AnalysisConsumer(pp, outDir, opts, plugins);
575 }
576 
577 //===----------------------------------------------------------------------===//
578 // Ubigraph Visualization.  FIXME: Move to separate file.
579 //===----------------------------------------------------------------------===//
580 
581 namespace {
582 
583 class UbigraphViz : public ExplodedNode::Auditor {
584   OwningPtr<raw_ostream> Out;
585   llvm::sys::Path Dir, Filename;
586   unsigned Cntr;
587 
588   typedef llvm::DenseMap<void*,unsigned> VMap;
589   VMap M;
590 
591 public:
592   UbigraphViz(raw_ostream *out, llvm::sys::Path& dir,
593               llvm::sys::Path& filename);
594 
595   ~UbigraphViz();
596 
597   virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst);
598 };
599 
600 } // end anonymous namespace
601 
602 static ExplodedNode::Auditor* CreateUbiViz() {
603   std::string ErrMsg;
604 
605   llvm::sys::Path Dir = llvm::sys::Path::GetTemporaryDirectory(&ErrMsg);
606   if (!ErrMsg.empty())
607     return 0;
608 
609   llvm::sys::Path Filename = Dir;
610   Filename.appendComponent("llvm_ubi");
611   Filename.makeUnique(true,&ErrMsg);
612 
613   if (!ErrMsg.empty())
614     return 0;
615 
616   llvm::errs() << "Writing '" << Filename.str() << "'.\n";
617 
618   OwningPtr<llvm::raw_fd_ostream> Stream;
619   Stream.reset(new llvm::raw_fd_ostream(Filename.c_str(), ErrMsg));
620 
621   if (!ErrMsg.empty())
622     return 0;
623 
624   return new UbigraphViz(Stream.take(), Dir, Filename);
625 }
626 
627 void UbigraphViz::AddEdge(ExplodedNode *Src, ExplodedNode *Dst) {
628 
629   assert (Src != Dst && "Self-edges are not allowed.");
630 
631   // Lookup the Src.  If it is a new node, it's a root.
632   VMap::iterator SrcI= M.find(Src);
633   unsigned SrcID;
634 
635   if (SrcI == M.end()) {
636     M[Src] = SrcID = Cntr++;
637     *Out << "('vertex', " << SrcID << ", ('color','#00ff00'))\n";
638   }
639   else
640     SrcID = SrcI->second;
641 
642   // Lookup the Dst.
643   VMap::iterator DstI= M.find(Dst);
644   unsigned DstID;
645 
646   if (DstI == M.end()) {
647     M[Dst] = DstID = Cntr++;
648     *Out << "('vertex', " << DstID << ")\n";
649   }
650   else {
651     // We have hit DstID before.  Change its style to reflect a cache hit.
652     DstID = DstI->second;
653     *Out << "('change_vertex_style', " << DstID << ", 1)\n";
654   }
655 
656   // Add the edge.
657   *Out << "('edge', " << SrcID << ", " << DstID
658        << ", ('arrow','true'), ('oriented', 'true'))\n";
659 }
660 
661 UbigraphViz::UbigraphViz(raw_ostream *out, llvm::sys::Path& dir,
662                          llvm::sys::Path& filename)
663   : Out(out), Dir(dir), Filename(filename), Cntr(0) {
664 
665   *Out << "('vertex_style_attribute', 0, ('shape', 'icosahedron'))\n";
666   *Out << "('vertex_style', 1, 0, ('shape', 'sphere'), ('color', '#ffcc66'),"
667           " ('size', '1.5'))\n";
668 }
669 
670 UbigraphViz::~UbigraphViz() {
671   Out.reset(0);
672   llvm::errs() << "Running 'ubiviz' program... ";
673   std::string ErrMsg;
674   llvm::sys::Path Ubiviz = llvm::sys::Program::FindProgramByName("ubiviz");
675   std::vector<const char*> args;
676   args.push_back(Ubiviz.c_str());
677   args.push_back(Filename.c_str());
678   args.push_back(0);
679 
680   if (llvm::sys::Program::ExecuteAndWait(Ubiviz, &args[0],0,0,0,0,&ErrMsg)) {
681     llvm::errs() << "Error viewing graph: " << ErrMsg << "\n";
682   }
683 
684   // Delete the directory.
685   Dir.eraseFromDisk(true);
686 }
687