contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/CheckerManager.cpp

   1 //===--- CheckerManager.cpp - Static Analyzer Checker Manager -------------===//
   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 // Defines the Static Analyzer Checker Manager.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  15 #include "clang/StaticAnalyzer/Core/CheckerProvider.h"
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  17 #include "clang/Analysis/ProgramPoint.h"
  18 #include "clang/AST/DeclBase.h"
  19
  20 using namespace clang;
  21 using namespace ento;
  22
  23 bool CheckerManager::hasPathSensitiveCheckers() const {
  24   return !StmtCheckers.empty()              ||
  25          !PreObjCMessageCheckers.empty()    ||
  26          !PostObjCMessageCheckers.empty()   ||
  27          !LocationCheckers.empty()          ||
  28          !BindCheckers.empty()              ||
  29          !EndAnalysisCheckers.empty()       ||
  30          !EndPathCheckers.empty()           ||
  31          !BranchConditionCheckers.empty()   ||
  32          !LiveSymbolsCheckers.empty()       ||
  33          !DeadSymbolsCheckers.empty()       ||
  34          !RegionChangesCheckers.empty()     ||
  35          !EvalAssumeCheckers.empty()        ||
  36          !EvalCallCheckers.empty();
  37 }
  38
  39 void CheckerManager::finishedCheckerRegistration() {
  40 #ifndef NDEBUG
  41   // Make sure that for every event that has listeners, there is at least
  42   // one dispatcher registered for it.
  43   for (llvm::DenseMap<EventTag, EventInfo>::iterator
  44          I = Events.begin(), E = Events.end(); I != E; ++I)
  45     assert(I->second.HasDispatcher && "No dispatcher registered for an event");
  46 #endif
  47 }
  48
  49 //===----------------------------------------------------------------------===//
  50 // Functions for running checkers for AST traversing..
  51 //===----------------------------------------------------------------------===//
  52
  53 void CheckerManager::runCheckersOnASTDecl(const Decl *D, AnalysisManager& mgr,
  54                                           BugReporter &BR) {
  55   assert(D);
  56
  57   unsigned DeclKind = D->getKind();
  58   CachedDeclCheckers *checkers = 0;
  59   CachedDeclCheckersMapTy::iterator CCI = CachedDeclCheckersMap.find(DeclKind);
  60   if (CCI != CachedDeclCheckersMap.end()) {
  61     checkers = &(CCI->second);
  62   } else {
  63     // Find the checkers that should run for this Decl and cache them.
  64     checkers = &CachedDeclCheckersMap[DeclKind];
  65     for (unsigned i = 0, e = DeclCheckers.size(); i != e; ++i) {
  66       DeclCheckerInfo &info = DeclCheckers[i];
  67       if (info.IsForDeclFn(D))
  68         checkers->push_back(info.CheckFn);
  69     }
  70   }
  71
  72   assert(checkers);
  73   for (CachedDeclCheckers::iterator
  74          I = checkers->begin(), E = checkers->end(); I != E; ++I)
  75     (*I)(D, mgr, BR);
  76 }
  77
  78 void CheckerManager::runCheckersOnASTBody(const Decl *D, AnalysisManager& mgr,
  79                                           BugReporter &BR) {
  80   assert(D && D->hasBody());
  81
  82   for (unsigned i = 0, e = BodyCheckers.size(); i != e; ++i)
  83     BodyCheckers[i](D, mgr, BR);
  84 }
  85
  86 //===----------------------------------------------------------------------===//
  87 // Functions for running checkers for path-sensitive checking.
  88 //===----------------------------------------------------------------------===//
  89
  90 template <typename CHECK_CTX>
  91 static void expandGraphWithCheckers(CHECK_CTX checkCtx,
  92                                     ExplodedNodeSet &Dst,
  93                                     const ExplodedNodeSet &Src) {
  94
  95   typename CHECK_CTX::CheckersTy::const_iterator
  96       I = checkCtx.checkers_begin(), E = checkCtx.checkers_end();
  97   if (I == E) {
  98     Dst.insert(Src);
  99     return;
 100   }
 101
 102   ExplodedNodeSet Tmp1, Tmp2;
 103   const ExplodedNodeSet *PrevSet = &Src;
 104
 105   for (; I != E; ++I) {
 106     ExplodedNodeSet *CurrSet = 0;
 107     if (I+1 == E)
 108       CurrSet = &Dst;
 109     else {
 110       CurrSet = (PrevSet == &Tmp1) ? &Tmp2 : &Tmp1;
 111       CurrSet->clear();
 112     }
 113
 114     for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
 115          NI != NE; ++NI)
 116       checkCtx.runChecker(*I, *CurrSet, *NI);
 117
 118     // Update which NodeSet is the current one.
 119     PrevSet = CurrSet;
 120   }
 121 }
 122
 123 namespace {
 124   struct CheckStmtContext {
 125     typedef llvm::SmallVectorImpl<CheckerManager::CheckStmtFunc> CheckersTy;
 126     bool IsPreVisit;
 127     const CheckersTy &Checkers;
 128     const Stmt *S;
 129     ExprEngine &Eng;
 130
 131     CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
 132     CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
 133
 134     CheckStmtContext(bool isPreVisit, const CheckersTy &checkers,
 135                      const Stmt *s, ExprEngine &eng)
 136       : IsPreVisit(isPreVisit), Checkers(checkers), S(s), Eng(eng) { }
 137
 138     void runChecker(CheckerManager::CheckStmtFunc checkFn,
 139                     ExplodedNodeSet &Dst, ExplodedNode *Pred) {
 140       // FIXME: Remove respondsToCallback from CheckerContext;
 141       CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
 142                        IsPreVisit ? ProgramPoint::PreStmtKind :
 143                                     ProgramPoint::PostStmtKind, 0, S);
 144       checkFn(S, C);
 145     }
 146   };
 147 }
 148
 149 /// \brief Run checkers for visiting Stmts.
 150 void CheckerManager::runCheckersForStmt(bool isPreVisit,
 151                                         ExplodedNodeSet &Dst,
 152                                         const ExplodedNodeSet &Src,
 153                                         const Stmt *S,
 154                                         ExprEngine &Eng) {
 155   CheckStmtContext C(isPreVisit, *getCachedStmtCheckersFor(S, isPreVisit),
 156                      S, Eng);
 157   expandGraphWithCheckers(C, Dst, Src);
 158 }
 159
 160 namespace {
 161   struct CheckObjCMessageContext {
 162     typedef std::vector<CheckerManager::CheckObjCMessageFunc> CheckersTy;
 163     bool IsPreVisit;
 164     const CheckersTy &Checkers;
 165     const ObjCMessage &Msg;
 166     ExprEngine &Eng;
 167
 168     CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
 169     CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
 170
 171     CheckObjCMessageContext(bool isPreVisit, const CheckersTy &checkers,
 172                             const ObjCMessage &msg, ExprEngine &eng)
 173       : IsPreVisit(isPreVisit), Checkers(checkers), Msg(msg), Eng(eng) { }
 174
 175     void runChecker(CheckerManager::CheckObjCMessageFunc checkFn,
 176                     ExplodedNodeSet &Dst, ExplodedNode *Pred) {
 177       CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
 178                        IsPreVisit ? ProgramPoint::PreStmtKind :
 179                                     ProgramPoint::PostStmtKind, 0,
 180                        Msg.getOriginExpr());
 181       checkFn(Msg, C);
 182     }
 183   };
 184 }
 185
 186 /// \brief Run checkers for visiting obj-c messages.
 187 void CheckerManager::runCheckersForObjCMessage(bool isPreVisit,
 188                                                ExplodedNodeSet &Dst,
 189                                                const ExplodedNodeSet &Src,
 190                                                const ObjCMessage &msg,
 191                                                ExprEngine &Eng) {
 192   CheckObjCMessageContext C(isPreVisit,
 193                             isPreVisit ? PreObjCMessageCheckers
 194                                        : PostObjCMessageCheckers,
 195                             msg, Eng);
 196   expandGraphWithCheckers(C, Dst, Src);
 197 }
 198
 199 namespace {
 200   struct CheckLocationContext {
 201     typedef std::vector<CheckerManager::CheckLocationFunc> CheckersTy;
 202     const CheckersTy &Checkers;
 203     SVal Loc;
 204     bool IsLoad;
 205     const Stmt *S;
 206     ExprEngine &Eng;
 207
 208     CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
 209     CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
 210
 211     CheckLocationContext(const CheckersTy &checkers,
 212                          SVal loc, bool isLoad, const Stmt *s, ExprEngine &eng)
 213       : Checkers(checkers), Loc(loc), IsLoad(isLoad), S(s), Eng(eng) { }
 214
 215     void runChecker(CheckerManager::CheckLocationFunc checkFn,
 216                     ExplodedNodeSet &Dst, ExplodedNode *Pred) {
 217       CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
 218                        IsLoad ? ProgramPoint::PreLoadKind :
 219                        ProgramPoint::PreStoreKind, 0, S);
 220       checkFn(Loc, IsLoad, C);
 221     }
 222   };
 223 }
 224
 225 /// \brief Run checkers for load/store of a location.
 226 void CheckerManager::runCheckersForLocation(ExplodedNodeSet &Dst,
 227                                             const ExplodedNodeSet &Src,
 228                                             SVal location, bool isLoad,
 229                                             const Stmt *S, ExprEngine &Eng) {
 230   CheckLocationContext C(LocationCheckers, location, isLoad, S, Eng);
 231   expandGraphWithCheckers(C, Dst, Src);
 232 }
 233
 234 namespace {
 235   struct CheckBindContext {
 236     typedef std::vector<CheckerManager::CheckBindFunc> CheckersTy;
 237     const CheckersTy &Checkers;
 238     SVal Loc;
 239     SVal Val;
 240     const Stmt *S;
 241     ExprEngine &Eng;
 242
 243     CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
 244     CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
 245
 246     CheckBindContext(const CheckersTy &checkers,
 247                      SVal loc, SVal val, const Stmt *s, ExprEngine &eng)
 248       : Checkers(checkers), Loc(loc), Val(val), S(s), Eng(eng) { }
 249
 250     void runChecker(CheckerManager::CheckBindFunc checkFn,
 251                     ExplodedNodeSet &Dst, ExplodedNode *Pred) {
 252       CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
 253                        ProgramPoint::PreStmtKind, 0, S);
 254       checkFn(Loc, Val, C);
 255     }
 256   };
 257 }
 258
 259 /// \brief Run checkers for binding of a value to a location.
 260 void CheckerManager::runCheckersForBind(ExplodedNodeSet &Dst,
 261                                         const ExplodedNodeSet &Src,
 262                                         SVal location, SVal val,
 263                                         const Stmt *S, ExprEngine &Eng) {
 264   CheckBindContext C(BindCheckers, location, val, S, Eng);
 265   expandGraphWithCheckers(C, Dst, Src);
 266 }
 267
 268 void CheckerManager::runCheckersForEndAnalysis(ExplodedGraph &G,
 269                                                BugReporter &BR,
 270                                                ExprEngine &Eng) {
 271   for (unsigned i = 0, e = EndAnalysisCheckers.size(); i != e; ++i)
 272     EndAnalysisCheckers[i](G, BR, Eng);
 273 }
 274
 275 /// \brief Run checkers for end of path.
 276 void CheckerManager::runCheckersForEndPath(EndOfFunctionNodeBuilder &B,
 277                                            ExprEngine &Eng) {
 278   for (unsigned i = 0, e = EndPathCheckers.size(); i != e; ++i) {
 279     CheckEndPathFunc fn = EndPathCheckers[i];
 280     EndOfFunctionNodeBuilder specialB = B.withCheckerTag(fn.Checker);
 281     fn(specialB, Eng);
 282   }
 283 }
 284
 285 /// \brief Run checkers for branch condition.
 286 void CheckerManager::runCheckersForBranchCondition(const Stmt *condition,
 287                                                    BranchNodeBuilder &B,
 288                                                    ExprEngine &Eng) {
 289   for (unsigned i = 0, e = BranchConditionCheckers.size(); i != e; ++i) {
 290     CheckBranchConditionFunc fn = BranchConditionCheckers[i];
 291     fn(condition, B, Eng);
 292   }
 293 }
 294
 295 /// \brief Run checkers for live symbols.
 296 void CheckerManager::runCheckersForLiveSymbols(const GRState *state,
 297                                                SymbolReaper &SymReaper) {
 298   for (unsigned i = 0, e = LiveSymbolsCheckers.size(); i != e; ++i)
 299     LiveSymbolsCheckers[i](state, SymReaper);
 300 }
 301
 302 namespace {
 303   struct CheckDeadSymbolsContext {
 304     typedef std::vector<CheckerManager::CheckDeadSymbolsFunc> CheckersTy;
 305     const CheckersTy &Checkers;
 306     SymbolReaper &SR;
 307     const Stmt *S;
 308     ExprEngine &Eng;
 309
 310     CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
 311     CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
 312
 313     CheckDeadSymbolsContext(const CheckersTy &checkers, SymbolReaper &sr,
 314                             const Stmt *s, ExprEngine &eng)
 315       : Checkers(checkers), SR(sr), S(s), Eng(eng) { }
 316
 317     void runChecker(CheckerManager::CheckDeadSymbolsFunc checkFn,
 318                     ExplodedNodeSet &Dst, ExplodedNode *Pred) {
 319       CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
 320                        ProgramPoint::PostPurgeDeadSymbolsKind, 0, S);
 321       checkFn(SR, C);
 322     }
 323   };
 324 }
 325
 326 /// \brief Run checkers for dead symbols.
 327 void CheckerManager::runCheckersForDeadSymbols(ExplodedNodeSet &Dst,
 328                                                const ExplodedNodeSet &Src,
 329                                                SymbolReaper &SymReaper,
 330                                                const Stmt *S,
 331                                                ExprEngine &Eng) {
 332   CheckDeadSymbolsContext C(DeadSymbolsCheckers, SymReaper, S, Eng);
 333   expandGraphWithCheckers(C, Dst, Src);
 334 }
 335
 336 /// \brief True if at least one checker wants to check region changes.
 337 bool CheckerManager::wantsRegionChangeUpdate(const GRState *state) {
 338   for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i)
 339     if (RegionChangesCheckers[i].WantUpdateFn(state))
 340       return true;
 341
 342   return false;
 343 }
 344
 345 /// \brief Run checkers for region changes.
 346 const GRState *
 347 CheckerManager::runCheckersForRegionChanges(const GRState *state,
 348                             const StoreManager::InvalidatedSymbols *invalidated,
 349                                             const MemRegion * const *Begin,
 350                                             const MemRegion * const *End) {
 351   for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i) {
 352     // If any checker declares the state infeasible (or if it starts that way),
 353     // bail out.
 354     if (!state)
 355       return NULL;
 356     state = RegionChangesCheckers[i].CheckFn(state, invalidated, Begin, End);
 357   }
 358   return state;
 359 }
 360
 361 /// \brief Run checkers for handling assumptions on symbolic values.
 362 const GRState *
 363 CheckerManager::runCheckersForEvalAssume(const GRState *state,
 364                                          SVal Cond, bool Assumption) {
 365   for (unsigned i = 0, e = EvalAssumeCheckers.size(); i != e; ++i) {
 366     // If any checker declares the state infeasible (or if it starts that way),
 367     // bail out.
 368     if (!state)
 369       return NULL;
 370     state = EvalAssumeCheckers[i](state, Cond, Assumption);
 371   }
 372   return state;
 373 }
 374
 375 /// \brief Run checkers for evaluating a call.
 376 /// Only one checker will evaluate the call.
 377 void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst,
 378                                             const ExplodedNodeSet &Src,
 379                                             const CallExpr *CE,
 380                                             ExprEngine &Eng,
 381                                             GraphExpander *defaultEval) {
 382   if (EvalCallCheckers.empty() && defaultEval == 0) {
 383     Dst.insert(Src);
 384     return;
 385   }
 386
 387   for (ExplodedNodeSet::iterator
 388          NI = Src.begin(), NE = Src.end(); NI != NE; ++NI) {
 389
 390     ExplodedNode *Pred = *NI;
 391     bool anyEvaluated = false;
 392     for (std::vector<EvalCallFunc>::iterator
 393            EI = EvalCallCheckers.begin(), EE = EvalCallCheckers.end();
 394          EI != EE; ++EI) {
 395       ExplodedNodeSet checkDst;
 396       CheckerContext C(checkDst, Eng.getBuilder(), Eng, Pred, EI->Checker,
 397                        ProgramPoint::PostStmtKind, 0, CE);
 398       bool evaluated = (*EI)(CE, C);
 399       assert(!(evaluated && anyEvaluated)
 400              && "There are more than one checkers evaluating the call");
 401       if (evaluated) {
 402         anyEvaluated = true;
 403         Dst.insert(checkDst);
 404 #ifdef NDEBUG
 405         break; // on release don't check that no other checker also evals.
 406 #endif
 407       }
 408     }
 409
 410     if (!anyEvaluated) {
 411       if (defaultEval)
 412         defaultEval->expandGraph(Dst, Pred);
 413       else
 414         Dst.insert(Pred);
 415     }
 416   }
 417 }
 418
 419 /// \brief Run checkers for the entire Translation Unit.
 420 void CheckerManager::runCheckersOnEndOfTranslationUnit(
 421                                                   const TranslationUnitDecl *TU,
 422                                                   AnalysisManager &mgr,
 423                                                   BugReporter &BR) {
 424   for (unsigned i = 0, e = EndOfTranslationUnitCheckers.size(); i != e; ++i)
 425     EndOfTranslationUnitCheckers[i](TU, mgr, BR);
 426 }
 427
 428 //===----------------------------------------------------------------------===//
 429 // Internal registration functions for AST traversing.
 430 //===----------------------------------------------------------------------===//
 431
 432 void CheckerManager::_registerForDecl(CheckDeclFunc checkfn,
 433                                       HandlesDeclFunc isForDeclFn) {
 434   DeclCheckerInfo info = { checkfn, isForDeclFn };
 435   DeclCheckers.push_back(info);
 436 }
 437
 438 void CheckerManager::_registerForBody(CheckDeclFunc checkfn) {
 439   BodyCheckers.push_back(checkfn);
 440 }
 441
 442 //===----------------------------------------------------------------------===//
 443 // Internal registration functions for path-sensitive checking.
 444 //===----------------------------------------------------------------------===//
 445
 446 void CheckerManager::_registerForPreStmt(CheckStmtFunc checkfn,
 447                                          HandlesStmtFunc isForStmtFn) {
 448   StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/true };
 449   StmtCheckers.push_back(info);
 450 }
 451 void CheckerManager::_registerForPostStmt(CheckStmtFunc checkfn,
 452                                           HandlesStmtFunc isForStmtFn) {
 453   StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/false };
 454   StmtCheckers.push_back(info);
 455 }
 456
 457 void CheckerManager::_registerForPreObjCMessage(CheckObjCMessageFunc checkfn) {
 458   PreObjCMessageCheckers.push_back(checkfn);
 459 }
 460 void CheckerManager::_registerForPostObjCMessage(CheckObjCMessageFunc checkfn) {
 461   PostObjCMessageCheckers.push_back(checkfn);
 462 }
 463
 464 void CheckerManager::_registerForLocation(CheckLocationFunc checkfn) {
 465   LocationCheckers.push_back(checkfn);
 466 }
 467
 468 void CheckerManager::_registerForBind(CheckBindFunc checkfn) {
 469   BindCheckers.push_back(checkfn);
 470 }
 471
 472 void CheckerManager::_registerForEndAnalysis(CheckEndAnalysisFunc checkfn) {
 473   EndAnalysisCheckers.push_back(checkfn);
 474 }
 475
 476 void CheckerManager::_registerForEndPath(CheckEndPathFunc checkfn) {
 477   EndPathCheckers.push_back(checkfn);
 478 }
 479
 480 void CheckerManager::_registerForBranchCondition(
 481                                              CheckBranchConditionFunc checkfn) {
 482   BranchConditionCheckers.push_back(checkfn);
 483 }
 484
 485 void CheckerManager::_registerForLiveSymbols(CheckLiveSymbolsFunc checkfn) {
 486   LiveSymbolsCheckers.push_back(checkfn);
 487 }
 488
 489 void CheckerManager::_registerForDeadSymbols(CheckDeadSymbolsFunc checkfn) {
 490   DeadSymbolsCheckers.push_back(checkfn);
 491 }
 492
 493 void CheckerManager::_registerForRegionChanges(CheckRegionChangesFunc checkfn,
 494                                      WantsRegionChangeUpdateFunc wantUpdateFn) {
 495   RegionChangesCheckerInfo info = {checkfn, wantUpdateFn};
 496   RegionChangesCheckers.push_back(info);
 497 }
 498
 499 void CheckerManager::_registerForEvalAssume(EvalAssumeFunc checkfn) {
 500   EvalAssumeCheckers.push_back(checkfn);
 501 }
 502
 503 void CheckerManager::_registerForEvalCall(EvalCallFunc checkfn) {
 504   EvalCallCheckers.push_back(checkfn);
 505 }
 506
 507 void CheckerManager::_registerForEndOfTranslationUnit(
 508                                             CheckEndOfTranslationUnit checkfn) {
 509   EndOfTranslationUnitCheckers.push_back(checkfn);
 510 }
 511
 512 //===----------------------------------------------------------------------===//
 513 // Implementation details.
 514 //===----------------------------------------------------------------------===//
 515
 516 CheckerManager::CachedStmtCheckers *
 517 CheckerManager::getCachedStmtCheckersFor(const Stmt *S, bool isPreVisit) {
 518   assert(S);
 519
 520   CachedStmtCheckersKey key(S->getStmtClass(), isPreVisit);
 521   CachedStmtCheckers *checkers = 0;
 522   CachedStmtCheckersMapTy::iterator CCI = CachedStmtCheckersMap.find(key);
 523   if (CCI != CachedStmtCheckersMap.end()) {
 524     checkers = &(CCI->second);
 525   } else {
 526     // Find the checkers that should run for this Stmt and cache them.
 527     checkers = &CachedStmtCheckersMap[key];
 528     for (unsigned i = 0, e = StmtCheckers.size(); i != e; ++i) {
 529       StmtCheckerInfo &info = StmtCheckers[i];
 530       if (info.IsPreVisit == isPreVisit && info.IsForStmtFn(S))
 531         checkers->push_back(info.CheckFn);
 532     }
 533   }
 534
 535   assert(checkers);
 536   return checkers;
 537 }
 538
 539 CheckerManager::~CheckerManager() {
 540   for (unsigned i = 0, e = CheckerDtors.size(); i != e; ++i)
 541     CheckerDtors[i]();
 542 }
 543
 544 // Anchor for the vtable.
 545 CheckerProvider::~CheckerProvider() { }
 546
 547 // Anchor for the vtable.
 548 GraphExpander::~GraphExpander() { }