clang/lib/Analysis/AnalysisDeclContext.cpp

   1 //===- AnalysisDeclContext.cpp - Analysis context for Path Sens analysis --===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines AnalysisDeclContext, a class that manages the analysis
  10 // context data for path sensitive analysis.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/Analysis/AnalysisDeclContext.h"
  15 #include "clang/AST/ASTContext.h"
  16 #include "clang/AST/Decl.h"
  17 #include "clang/AST/DeclBase.h"
  18 #include "clang/AST/DeclCXX.h"
  19 #include "clang/AST/DeclObjC.h"
  20 #include "clang/AST/DeclTemplate.h"
  21 #include "clang/AST/Expr.h"
  22 #include "clang/AST/LambdaCapture.h"
  23 #include "clang/AST/ParentMap.h"
  24 #include "clang/AST/PrettyPrinter.h"
  25 #include "clang/AST/Stmt.h"
  26 #include "clang/AST/StmtCXX.h"
  27 #include "clang/AST/StmtVisitor.h"
  28 #include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
  29 #include "clang/Analysis/BodyFarm.h"
  30 #include "clang/Analysis/CFG.h"
  31 #include "clang/Analysis/CFGStmtMap.h"
  32 #include "clang/Analysis/Support/BumpVector.h"
  33 #include "clang/Basic/JsonSupport.h"
  34 #include "clang/Basic/LLVM.h"
  35 #include "clang/Basic/SourceLocation.h"
  36 #include "clang/Basic/SourceManager.h"
  37 #include "llvm/ADT/DenseMap.h"
  38 #include "llvm/ADT/FoldingSet.h"
  39 #include "llvm/ADT/STLExtras.h"
  40 #include "llvm/ADT/SmallPtrSet.h"
  41 #include "llvm/ADT/iterator_range.h"
  42 #include "llvm/Support/Allocator.h"
  43 #include "llvm/Support/Casting.h"
  44 #include "llvm/Support/Compiler.h"
  45 #include "llvm/Support/ErrorHandling.h"
  46 #include "llvm/Support/SaveAndRestore.h"
  47 #include "llvm/Support/raw_ostream.h"
  48 #include <cassert>
  49 #include <memory>
  50
  51 using namespace clang;
  52
  53 using ManagedAnalysisMap = llvm::DenseMap<const void *, std::unique_ptr<ManagedAnalysis>>;
  54
  55 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *ADCMgr,
  56                                          const Decl *D,
  57                                          const CFG::BuildOptions &Options)
  58     : ADCMgr(ADCMgr), D(D), cfgBuildOptions(Options) {
  59   cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
  60 }
  61
  62 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *ADCMgr,
  63                                          const Decl *D)
  64     : ADCMgr(ADCMgr), D(D) {
  65   cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
  66 }
  67
  68 AnalysisDeclContextManager::AnalysisDeclContextManager(
  69     ASTContext &ASTCtx, bool useUnoptimizedCFG, bool addImplicitDtors,
  70     bool addInitializers, bool addTemporaryDtors, bool addLifetime,
  71     bool addLoopExit, bool addScopes, bool synthesizeBodies,
  72     bool addStaticInitBranch, bool addCXXNewAllocator,
  73     bool addRichCXXConstructors, bool markElidedCXXConstructors,
  74     bool addVirtualBaseBranches, CodeInjector *injector)
  75     : Injector(injector), FunctionBodyFarm(ASTCtx, injector),
  76       SynthesizeBodies(synthesizeBodies) {
  77   cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG;
  78   cfgBuildOptions.AddImplicitDtors = addImplicitDtors;
  79   cfgBuildOptions.AddInitializers = addInitializers;
  80   cfgBuildOptions.AddTemporaryDtors = addTemporaryDtors;
  81   cfgBuildOptions.AddLifetime = addLifetime;
  82   cfgBuildOptions.AddLoopExit = addLoopExit;
  83   cfgBuildOptions.AddScopes = addScopes;
  84   cfgBuildOptions.AddStaticInitBranches = addStaticInitBranch;
  85   cfgBuildOptions.AddCXXNewAllocator = addCXXNewAllocator;
  86   cfgBuildOptions.AddRichCXXConstructors = addRichCXXConstructors;
  87   cfgBuildOptions.MarkElidedCXXConstructors = markElidedCXXConstructors;
  88   cfgBuildOptions.AddVirtualBaseBranches = addVirtualBaseBranches;
  89 }
  90
  91 void AnalysisDeclContextManager::clear() { Contexts.clear(); }
  92
  93 Stmt *AnalysisDeclContext::getBody(bool &IsAutosynthesized) const {
  94   IsAutosynthesized = false;
  95   if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
  96     Stmt *Body = FD->getBody();
  97     if (auto *CoroBody = dyn_cast_or_null<CoroutineBodyStmt>(Body))
  98       Body = CoroBody->getBody();
  99     if (ADCMgr && ADCMgr->synthesizeBodies()) {
 100       Stmt *SynthesizedBody = ADCMgr->getBodyFarm().getBody(FD);
 101       if (SynthesizedBody) {
 102         Body = SynthesizedBody;
 103         IsAutosynthesized = true;
 104       }
 105     }
 106     return Body;
 107   }
 108   else if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) {
 109     Stmt *Body = MD->getBody();
 110     if (ADCMgr && ADCMgr->synthesizeBodies()) {
 111       Stmt *SynthesizedBody = ADCMgr->getBodyFarm().getBody(MD);
 112       if (SynthesizedBody) {
 113         Body = SynthesizedBody;
 114         IsAutosynthesized = true;
 115       }
 116     }
 117     return Body;
 118   } else if (const auto *BD = dyn_cast<BlockDecl>(D))
 119     return BD->getBody();
 120   else if (const auto *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
 121     return FunTmpl->getTemplatedDecl()->getBody();
 122
 123   llvm_unreachable("unknown code decl");
 124 }
 125
 126 Stmt *AnalysisDeclContext::getBody() const {
 127   bool Tmp;
 128   return getBody(Tmp);
 129 }
 130
 131 bool AnalysisDeclContext::isBodyAutosynthesized() const {
 132   bool Tmp;
 133   getBody(Tmp);
 134   return Tmp;
 135 }
 136
 137 bool AnalysisDeclContext::isBodyAutosynthesizedFromModelFile() const {
 138   bool Tmp;
 139   Stmt *Body = getBody(Tmp);
 140   return Tmp && Body->getBeginLoc().isValid();
 141 }
 142
 143 /// Returns true if \param VD is an Objective-C implicit 'self' parameter.
 144 static bool isSelfDecl(const VarDecl *VD) {
 145   return isa_and_nonnull<ImplicitParamDecl>(VD) && VD->getName() == "self";
 146 }
 147
 148 const ImplicitParamDecl *AnalysisDeclContext::getSelfDecl() const {
 149   if (const auto *MD = dyn_cast<ObjCMethodDecl>(D))
 150     return MD->getSelfDecl();
 151   if (const auto *BD = dyn_cast<BlockDecl>(D)) {
 152     // See if 'self' was captured by the block.
 153     for (const auto &I : BD->captures()) {
 154       const VarDecl *VD = I.getVariable();
 155       if (isSelfDecl(VD))
 156         return dyn_cast<ImplicitParamDecl>(VD);
 157     }
 158   }
 159
 160   auto *CXXMethod = dyn_cast<CXXMethodDecl>(D);
 161   if (!CXXMethod)
 162     return nullptr;
 163
 164   const CXXRecordDecl *parent = CXXMethod->getParent();
 165   if (!parent->isLambda())
 166     return nullptr;
 167
 168   for (const auto &LC : parent->captures()) {
 169     if (!LC.capturesVariable())
 170       continue;
 171
 172     ValueDecl *VD = LC.getCapturedVar();
 173     if (isSelfDecl(dyn_cast<VarDecl>(VD)))
 174       return dyn_cast<ImplicitParamDecl>(VD);
 175   }
 176
 177   return nullptr;
 178 }
 179
 180 void AnalysisDeclContext::registerForcedBlockExpression(const Stmt *stmt) {
 181   if (!forcedBlkExprs)
 182     forcedBlkExprs = new CFG::BuildOptions::ForcedBlkExprs();
 183   // Default construct an entry for 'stmt'.
 184   if (const auto *e = dyn_cast<Expr>(stmt))
 185     stmt = e->IgnoreParens();
 186   (void) (*forcedBlkExprs)[stmt];
 187 }
 188
 189 const CFGBlock *
 190 AnalysisDeclContext::getBlockForRegisteredExpression(const Stmt *stmt) {
 191   assert(forcedBlkExprs);
 192   if (const auto *e = dyn_cast<Expr>(stmt))
 193     stmt = e->IgnoreParens();
 194   CFG::BuildOptions::ForcedBlkExprs::const_iterator itr =
 195     forcedBlkExprs->find(stmt);
 196   assert(itr != forcedBlkExprs->end());
 197   return itr->second;
 198 }
 199
 200 /// Add each synthetic statement in the CFG to the parent map, using the
 201 /// source statement's parent.
 202 static void addParentsForSyntheticStmts(const CFG *TheCFG, ParentMap &PM) {
 203   if (!TheCFG)
 204     return;
 205
 206   for (CFG::synthetic_stmt_iterator I = TheCFG->synthetic_stmt_begin(),
 207                                     E = TheCFG->synthetic_stmt_end();
 208        I != E; ++I) {
 209     PM.setParent(I->first, PM.getParent(I->second));
 210   }
 211 }
 212
 213 CFG *AnalysisDeclContext::getCFG() {
 214   if (!cfgBuildOptions.PruneTriviallyFalseEdges)
 215     return getUnoptimizedCFG();
 216
 217   if (!builtCFG) {
 218     cfg = CFG::buildCFG(D, getBody(), &D->getASTContext(), cfgBuildOptions);
 219     // Even when the cfg is not successfully built, we don't
 220     // want to try building it again.
 221     builtCFG = true;
 222
 223     if (PM)
 224       addParentsForSyntheticStmts(cfg.get(), *PM);
 225
 226     // The Observer should only observe one build of the CFG.
 227     getCFGBuildOptions().Observer = nullptr;
 228   }
 229   return cfg.get();
 230 }
 231
 232 CFG *AnalysisDeclContext::getUnoptimizedCFG() {
 233   if (!builtCompleteCFG) {
 234     SaveAndRestore NotPrune(cfgBuildOptions.PruneTriviallyFalseEdges, false);
 235     completeCFG =
 236         CFG::buildCFG(D, getBody(), &D->getASTContext(), cfgBuildOptions);
 237     // Even when the cfg is not successfully built, we don't
 238     // want to try building it again.
 239     builtCompleteCFG = true;
 240
 241     if (PM)
 242       addParentsForSyntheticStmts(completeCFG.get(), *PM);
 243
 244     // The Observer should only observe one build of the CFG.
 245     getCFGBuildOptions().Observer = nullptr;
 246   }
 247   return completeCFG.get();
 248 }
 249
 250 CFGStmtMap *AnalysisDeclContext::getCFGStmtMap() {
 251   if (cfgStmtMap)
 252     return cfgStmtMap.get();
 253
 254   if (CFG *c = getCFG()) {
 255     cfgStmtMap.reset(CFGStmtMap::Build(c, &getParentMap()));
 256     return cfgStmtMap.get();
 257   }
 258
 259   return nullptr;
 260 }
 261
 262 CFGReverseBlockReachabilityAnalysis *AnalysisDeclContext::getCFGReachablityAnalysis() {
 263   if (CFA)
 264     return CFA.get();
 265
 266   if (CFG *c = getCFG()) {
 267     CFA.reset(new CFGReverseBlockReachabilityAnalysis(*c));
 268     return CFA.get();
 269   }
 270
 271   return nullptr;
 272 }
 273
 274 void AnalysisDeclContext::dumpCFG(bool ShowColors) {
 275   getCFG()->dump(getASTContext().getLangOpts(), ShowColors);
 276 }
 277
 278 ParentMap &AnalysisDeclContext::getParentMap() {
 279   if (!PM) {
 280     PM.reset(new ParentMap(getBody()));
 281     if (const auto *C = dyn_cast<CXXConstructorDecl>(getDecl())) {
 282       for (const auto *I : C->inits()) {
 283         PM->addStmt(I->getInit());
 284       }
 285     }
 286     if (builtCFG)
 287       addParentsForSyntheticStmts(getCFG(), *PM);
 288     if (builtCompleteCFG)
 289       addParentsForSyntheticStmts(getUnoptimizedCFG(), *PM);
 290   }
 291   return *PM;
 292 }
 293
 294 AnalysisDeclContext *AnalysisDeclContextManager::getContext(const Decl *D) {
 295   if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
 296     // Calling 'hasBody' replaces 'FD' in place with the FunctionDecl
 297     // that has the body.
 298     FD->hasBody(FD);
 299     D = FD;
 300   }
 301
 302   std::unique_ptr<AnalysisDeclContext> &AC = Contexts[D];
 303   if (!AC)
 304     AC = std::make_unique<AnalysisDeclContext>(this, D, cfgBuildOptions);
 305   return AC.get();
 306 }
 307
 308 BodyFarm &AnalysisDeclContextManager::getBodyFarm() { return FunctionBodyFarm; }
 309
 310 const StackFrameContext *
 311 AnalysisDeclContext::getStackFrame(const LocationContext *ParentLC,
 312                                    const Stmt *S, const CFGBlock *Blk,
 313                                    unsigned BlockCount, unsigned Index) {
 314   return getLocationContextManager().getStackFrame(this, ParentLC, S, Blk,
 315                                                    BlockCount, Index);
 316 }
 317
 318 const BlockInvocationContext *AnalysisDeclContext::getBlockInvocationContext(
 319     const LocationContext *ParentLC, const BlockDecl *BD, const void *Data) {
 320   return getLocationContextManager().getBlockInvocationContext(this, ParentLC,
 321                                                                BD, Data);
 322 }
 323
 324 bool AnalysisDeclContext::isInStdNamespace(const Decl *D) {
 325   const DeclContext *DC = D->getDeclContext()->getEnclosingNamespaceContext();
 326   const auto *ND = dyn_cast<NamespaceDecl>(DC);
 327   if (!ND)
 328     return false;
 329
 330   while (const DeclContext *Parent = ND->getParent()) {
 331     if (!isa<NamespaceDecl>(Parent))
 332       break;
 333     ND = cast<NamespaceDecl>(Parent);
 334   }
 335
 336   return ND->isStdNamespace();
 337 }
 338
 339 std::string AnalysisDeclContext::getFunctionName(const Decl *D) {
 340   std::string Str;
 341   llvm::raw_string_ostream OS(Str);
 342   const ASTContext &Ctx = D->getASTContext();
 343
 344   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
 345     OS << FD->getQualifiedNameAsString();
 346
 347     // In C++, there are overloads.
 348
 349     if (Ctx.getLangOpts().CPlusPlus) {
 350       OS << '(';
 351       for (const auto &P : FD->parameters()) {
 352         if (P != *FD->param_begin())
 353           OS << ", ";
 354         OS << P->getType();
 355       }
 356       OS << ')';
 357     }
 358
 359   } else if (isa<BlockDecl>(D)) {
 360     PresumedLoc Loc = Ctx.getSourceManager().getPresumedLoc(D->getLocation());
 361
 362     if (Loc.isValid()) {
 363       OS << "block (line: " << Loc.getLine() << ", col: " << Loc.getColumn()
 364          << ')';
 365     }
 366
 367   } else if (const ObjCMethodDecl *OMD = dyn_cast<ObjCMethodDecl>(D)) {
 368
 369     // FIXME: copy-pasted from CGDebugInfo.cpp.
 370     OS << (OMD->isInstanceMethod() ? '-' : '+') << '[';
 371     const DeclContext *DC = OMD->getDeclContext();
 372     if (const auto *OID = dyn_cast<ObjCImplementationDecl>(DC)) {
 373       OS << OID->getName();
 374     } else if (const auto *OID = dyn_cast<ObjCInterfaceDecl>(DC)) {
 375       OS << OID->getName();
 376     } else if (const auto *OC = dyn_cast<ObjCCategoryDecl>(DC)) {
 377       if (OC->IsClassExtension()) {
 378         OS << OC->getClassInterface()->getName();
 379       } else {
 380         OS << OC->getIdentifier()->getNameStart() << '('
 381            << OC->getIdentifier()->getNameStart() << ')';
 382       }
 383     } else if (const auto *OCD = dyn_cast<ObjCCategoryImplDecl>(DC)) {
 384       OS << OCD->getClassInterface()->getName() << '(' << OCD->getName() << ')';
 385     }
 386     OS << ' ' << OMD->getSelector().getAsString() << ']';
 387   }
 388
 389   return Str;
 390 }
 391
 392 LocationContextManager &AnalysisDeclContext::getLocationContextManager() {
 393   assert(
 394       ADCMgr &&
 395       "Cannot create LocationContexts without an AnalysisDeclContextManager!");
 396   return ADCMgr->getLocationContextManager();
 397 }
 398
 399 //===----------------------------------------------------------------------===//
 400 // FoldingSet profiling.
 401 //===----------------------------------------------------------------------===//
 402
 403 void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID,
 404                                     ContextKind ck,
 405                                     AnalysisDeclContext *ctx,
 406                                     const LocationContext *parent,
 407                                     const void *data) {
 408   ID.AddInteger(ck);
 409   ID.AddPointer(ctx);
 410   ID.AddPointer(parent);
 411   ID.AddPointer(data);
 412 }
 413
 414 void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) {
 415   Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block,
 416           BlockCount, Index);
 417 }
 418
 419 void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) {
 420   Profile(ID, getAnalysisDeclContext(), getParent(), BD, Data);
 421 }
 422
 423 //===----------------------------------------------------------------------===//
 424 // LocationContext creation.
 425 //===----------------------------------------------------------------------===//
 426
 427 const StackFrameContext *LocationContextManager::getStackFrame(
 428     AnalysisDeclContext *ctx, const LocationContext *parent, const Stmt *s,
 429     const CFGBlock *blk, unsigned blockCount, unsigned idx) {
 430   llvm::FoldingSetNodeID ID;
 431   StackFrameContext::Profile(ID, ctx, parent, s, blk, blockCount, idx);
 432   void *InsertPos;
 433   auto *L =
 434    cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
 435   if (!L) {
 436     L = new StackFrameContext(ctx, parent, s, blk, blockCount, idx, ++NewID);
 437     Contexts.InsertNode(L, InsertPos);
 438   }
 439   return L;
 440 }
 441
 442 const BlockInvocationContext *LocationContextManager::getBlockInvocationContext(
 443     AnalysisDeclContext *ADC, const LocationContext *ParentLC,
 444     const BlockDecl *BD, const void *Data) {
 445   llvm::FoldingSetNodeID ID;
 446   BlockInvocationContext::Profile(ID, ADC, ParentLC, BD, Data);
 447   void *InsertPos;
 448   auto *L =
 449     cast_or_null<BlockInvocationContext>(Contexts.FindNodeOrInsertPos(ID,
 450                                                                     InsertPos));
 451   if (!L) {
 452     L = new BlockInvocationContext(ADC, ParentLC, BD, Data, ++NewID);
 453     Contexts.InsertNode(L, InsertPos);
 454   }
 455   return L;
 456 }
 457
 458 //===----------------------------------------------------------------------===//
 459 // LocationContext methods.
 460 //===----------------------------------------------------------------------===//
 461
 462 const StackFrameContext *LocationContext::getStackFrame() const {
 463   const LocationContext *LC = this;
 464   while (LC) {
 465     if (const auto *SFC = dyn_cast<StackFrameContext>(LC))
 466       return SFC;
 467     LC = LC->getParent();
 468   }
 469   return nullptr;
 470 }
 471
 472 bool LocationContext::inTopFrame() const {
 473   return getStackFrame()->inTopFrame();
 474 }
 475
 476 bool LocationContext::isParentOf(const LocationContext *LC) const {
 477   do {
 478     const LocationContext *Parent = LC->getParent();
 479     if (Parent == this)
 480       return true;
 481     else
 482       LC = Parent;
 483   } while (LC);
 484
 485   return false;
 486 }
 487
 488 static void printLocation(raw_ostream &Out, const SourceManager &SM,
 489                           SourceLocation Loc) {
 490   if (Loc.isFileID() && SM.isInMainFile(Loc))
 491     Out << SM.getExpansionLineNumber(Loc);
 492   else
 493     Loc.print(Out, SM);
 494 }
 495
 496 void LocationContext::dumpStack(raw_ostream &Out) const {
 497   ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
 498   PrintingPolicy PP(Ctx.getLangOpts());
 499   PP.TerseOutput = 1;
 500
 501   const SourceManager &SM =
 502       getAnalysisDeclContext()->getASTContext().getSourceManager();
 503
 504   unsigned Frame = 0;
 505   for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
 506     switch (LCtx->getKind()) {
 507     case StackFrame:
 508       Out << "\t#" << Frame << ' ';
 509       ++Frame;
 510       if (const auto *D = dyn_cast<NamedDecl>(LCtx->getDecl()))
 511         Out << "Calling " << AnalysisDeclContext::getFunctionName(D);
 512       else
 513         Out << "Calling anonymous code";
 514       if (const Stmt *S = cast<StackFrameContext>(LCtx)->getCallSite()) {
 515         Out << " at line ";
 516         printLocation(Out, SM, S->getBeginLoc());
 517       }
 518       break;
 519     case Block:
 520       Out << "Invoking block";
 521       if (const Decl *D = cast<BlockInvocationContext>(LCtx)->getDecl()) {
 522         Out << " defined at line ";
 523         printLocation(Out, SM, D->getBeginLoc());
 524       }
 525       break;
 526     }
 527     Out << '\n';
 528   }
 529 }
 530
 531 void LocationContext::printJson(raw_ostream &Out, const char *NL,
 532                                 unsigned int Space, bool IsDot,
 533                                 std::function<void(const LocationContext *)>
 534                                     printMoreInfoPerContext) const {
 535   ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
 536   PrintingPolicy PP(Ctx.getLangOpts());
 537   PP.TerseOutput = 1;
 538
 539   const SourceManager &SM =
 540       getAnalysisDeclContext()->getASTContext().getSourceManager();
 541
 542   unsigned Frame = 0;
 543   for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
 544     Indent(Out, Space, IsDot)
 545         << "{ \"lctx_id\": " << LCtx->getID() << ", \"location_context\": \"";
 546     switch (LCtx->getKind()) {
 547     case StackFrame:
 548       Out << '#' << Frame << " Call\", \"calling\": \"";
 549       ++Frame;
 550       if (const auto *D = dyn_cast<NamedDecl>(LCtx->getDecl()))
 551         Out << D->getQualifiedNameAsString();
 552       else
 553         Out << "anonymous code";
 554
 555       Out << "\", \"location\": ";
 556       if (const Stmt *S = cast<StackFrameContext>(LCtx)->getCallSite()) {
 557         printSourceLocationAsJson(Out, S->getBeginLoc(), SM);
 558       } else {
 559         Out << "null";
 560       }
 561
 562       Out << ", \"items\": ";
 563       break;
 564     case Block:
 565       Out << "Invoking block\" ";
 566       if (const Decl *D = cast<BlockInvocationContext>(LCtx)->getDecl()) {
 567         Out << ", \"location\": ";
 568         printSourceLocationAsJson(Out, D->getBeginLoc(), SM);
 569         Out << ' ';
 570       }
 571       break;
 572     }
 573
 574     printMoreInfoPerContext(LCtx);
 575
 576     Out << '}';
 577     if (LCtx->getParent())
 578       Out << ',';
 579     Out << NL;
 580   }
 581 }
 582
 583 LLVM_DUMP_METHOD void LocationContext::dump() const { printJson(llvm::errs()); }
 584
 585 //===----------------------------------------------------------------------===//
 586 // Lazily generated map to query the external variables referenced by a Block.
 587 //===----------------------------------------------------------------------===//
 588
 589 namespace {
 590
 591 class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{
 592   BumpVector<const VarDecl *> &BEVals;
 593   BumpVectorContext &BC;
 594   llvm::SmallPtrSet<const VarDecl *, 4> Visited;
 595   llvm::SmallPtrSet<const DeclContext *, 4> IgnoredContexts;
 596
 597 public:
 598   FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals,
 599                             BumpVectorContext &bc)
 600       : BEVals(bevals), BC(bc) {}
 601
 602   void VisitStmt(Stmt *S) {
 603     for (auto *Child : S->children())
 604       if (Child)
 605         Visit(Child);
 606   }
 607
 608   void VisitDeclRefExpr(DeclRefExpr *DR) {
 609     // Non-local variables are also directly modified.
 610     if (const auto *VD = dyn_cast<VarDecl>(DR->getDecl())) {
 611       if (!VD->hasLocalStorage()) {
 612         if (Visited.insert(VD).second)
 613           BEVals.push_back(VD, BC);
 614       }
 615     }
 616   }
 617
 618   void VisitBlockExpr(BlockExpr *BR) {
 619     // Blocks containing blocks can transitively capture more variables.
 620     IgnoredContexts.insert(BR->getBlockDecl());
 621     Visit(BR->getBlockDecl()->getBody());
 622   }
 623
 624   void VisitPseudoObjectExpr(PseudoObjectExpr *PE) {
 625     for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(),
 626          et = PE->semantics_end(); it != et; ++it) {
 627       Expr *Semantic = *it;
 628       if (auto *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
 629         Semantic = OVE->getSourceExpr();
 630       Visit(Semantic);
 631     }
 632   }
 633 };
 634
 635 } // namespace
 636
 637 using DeclVec = BumpVector<const VarDecl *>;
 638
 639 static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD,
 640                                               void *&Vec,
 641                                               llvm::BumpPtrAllocator &A) {
 642   if (Vec)
 643     return (DeclVec*) Vec;
 644
 645   BumpVectorContext BC(A);
 646   DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>();
 647   new (BV) DeclVec(BC, 10);
 648
 649   // Go through the capture list.
 650   for (const auto &CI : BD->captures()) {
 651     BV->push_back(CI.getVariable(), BC);
 652   }
 653
 654   // Find the referenced global/static variables.
 655   FindBlockDeclRefExprsVals F(*BV, BC);
 656   F.Visit(BD->getBody());
 657
 658   Vec = BV;
 659   return BV;
 660 }
 661
 662 llvm::iterator_range<AnalysisDeclContext::referenced_decls_iterator>
 663 AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) {
 664   if (!ReferencedBlockVars)
 665     ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>();
 666
 667   const DeclVec *V =
 668       LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A);
 669   return llvm::make_range(V->begin(), V->end());
 670 }
 671
 672 std::unique_ptr<ManagedAnalysis> &AnalysisDeclContext::getAnalysisImpl(const void *tag) {
 673   if (!ManagedAnalyses)
 674     ManagedAnalyses = new ManagedAnalysisMap();
 675   ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
 676   return (*M)[tag];
 677 }
 678
 679 //===----------------------------------------------------------------------===//
 680 // Cleanup.
 681 //===----------------------------------------------------------------------===//
 682
 683 ManagedAnalysis::~ManagedAnalysis() = default;
 684
 685 AnalysisDeclContext::~AnalysisDeclContext() {
 686   delete forcedBlkExprs;
 687   delete ReferencedBlockVars;
 688   delete (ManagedAnalysisMap*) ManagedAnalyses;
 689 }
 690
 691 LocationContext::~LocationContext() = default;
 692
 693 LocationContextManager::~LocationContextManager() {
 694   clear();
 695 }
 696
 697 void LocationContextManager::clear() {
 698   for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(),
 699        E = Contexts.end(); I != E; ) {
 700     LocationContext *LC = &*I;
 701     ++I;
 702     delete LC;
 703   }
 704   Contexts.clear();
 705 }