[CFG] [analyzer] NFC: Allow more complicated construction contexts.

[NoQ]

Summary

ConstructionContexts introduced in D42672 are an additional piece of information included with CFGConstructor elements that help the client of the CFG (specifically, the static analyzer - it's off for other clients) to understand where the newly constructed object is stored. For now ConstructionContext was only capable of containing a single statement, such as a DeclStmt (if it's a variable's constructor) or a CXXNewExpr (if it's a heap object) or a CXXCtorInitializer (if it's a field or a base-class instance - this isn't a statement however) or a CXXBindTemporaryExpr (if it's a temporary that requires a destructor call).

This patch continues the effort as planned. In order to handle more complex constructions, richer construction contexts are required. This patch adds two new possibilities (without immediately using any of them):

• to nest construction contexts into each other, as a linked list that is constructed gradually during AST traversal;
• to maintain construction contexts for multiple constructors simultaneously.

I'd give an example of how it's planned to be used here, and post a separate revision with actually using them that way. Consider the ternary operator example from http://lists.llvm.org/pipermail/cfe-dev/2018-February/056898.html:

1    class C {
2    public:
3      C(int) {}
4      ~C() {}
5    };
6
7    void foo(int coin) {
8      const C &c = coin ? C(1) : C(2);
9    }

DeclStmt 0x7fc1e20023e0 <line:8:3, col:34>
`-VarDecl 0x7fc1e2001dc8 <col:3, col:33> col:12 c 'const C &' cinit
  `-ExprWithCleanups 0x7fc1e2002370 <col:16, col:33> 'const C' lvalue
    `-MaterializeTemporaryExpr 0x7fc1e2002340 <col:16, col:33> 'const C' lvalue extended by Var 0x7fc1e2001dc8 'c' 'const C &'
      `-ImplicitCastExpr 0x7fc1e2002328 <col:16, col:33> 'const C' <NoOp>
        `-ConditionalOperator 0x7fc1e20022f8 <col:16, col:33> 'C'
          |-ImplicitCastExpr 0x7fc1e2002170 <col:16> 'bool' <IntegralToBoolean>
          | `-ImplicitCastExpr 0x7fc1e2002158 <col:16> 'int' <LValueToRValue>
          |   `-DeclRefExpr 0x7fc1e2001e28 <col:16> 'int' lvalue ParmVar 0x7fc1e2001c18 'coin' 'int'
          |-CXXBindTemporaryExpr 0x7fc1e2002248 <col:23, col:26> 'C' (CXXTemporary 0x7fc1e2002240)
          | `-CXXConstructExpr 0x7fc1e2002208 <col:23, col:26> 'C' 'void (const C &) noexcept' elidable
          |   `-MaterializeTemporaryExpr 0x7fc1e20021a0 <col:23, col:26> 'const C' lvalue
          |     `-ImplicitCastExpr 0x7fc1e2002188 <col:23, col:26> 'const C' <NoOp>
          |       `-CXXFunctionalCastExpr 0x7fc1e2002078 <col:23, col:26> 'C' functional cast to class C <ConstructorConversion>
          |         `-CXXBindTemporaryExpr 0x7fc1e2002058 <col:23, col:26> 'C' (CXXTemporary 0x7fc1e2002050)
          |           `-CXXConstructExpr 0x7fc1e2002018 <col:23, col:26> 'C' 'void (int)'
          |             `-IntegerLiteral 0x7fc1e2001e60 <col:25> 'int' 1
          `-CXXBindTemporaryExpr 0x7fc1e20022d8 <col:30, col:33> 'C' (CXXTemporary 0x7fc1e20022d0)
            `-CXXConstructExpr 0x7fc1e2002298 <col:30, col:33> 'C' 'void (const C &) noexcept' elidable
              `-MaterializeTemporaryExpr 0x7fc1e2002280 <col:30, col:33> 'const C' lvalue
                `-ImplicitCastExpr 0x7fc1e2002268 <col:30, col:33> 'const C' <NoOp>
                  `-CXXFunctionalCastExpr 0x7fc1e2002130 <col:30, col:33> 'C' functional cast to class C <ConstructorConversion>
                    `-CXXBindTemporaryExpr 0x7fc1e2002110 <col:30, col:33> 'C' (CXXTemporary 0x7fc1e2002108)
                      `-CXXConstructExpr 0x7fc1e20020d0 <col:30, col:33> 'C' 'void (int)'
                        `-IntegerLiteral 0x7fc1e20020b0 <col:32> 'int' 2

Look at the two elidable copy-constructors. As explained in the aforementioned mail, if we want the CFG client to understand how lifetime extension works, we need to include both the surrounding CXXBindTemporaryExpr (0x7fc1e2002248 for the first constructor and 0x7fc1e20022d8 for the second constructor) and the surrounding MaterializeTemporaryExpr (0x7fc1e2002340 for both constructors) in the construction context.

While traversing the AST in findConstructionContexts() (formerly known as EnterConstructionContextIfNecessary()), we'll first encounter MaterializeTemporaryExpr 0x7fc1e2002340. We'll create a ConstructionContext for MaterializeTemporaryExpr and set it as the current ContextSoFar. Then we'll encounter the first CXXBindTemporaryExpr and change ContextSoFar to the new context that has CXXBindTemporaryExpr as the trigger statement and the old context as its parent. Then we'll see the constructor within the CXXBindTemporaryExpr and realize that we've just built its construction context. Then we'd pop out of the CXXBindTemporaryExpr and restore the old MaterializeTemporaryExpr-based context and go to another branch of our ConditionalOperator. Here we'd see the other CXXBindTemporaryExpr, for which we'd do the same thing. With that, both constructors would have their contexts set (simultaneously!), and their contexts would be triggered by their respective CXXBindTemporaryExpr and "previously triggered" (through the parent context) by their common MaterializeTemporaryExpr. Then during normal visit, we'd encounter both constructors and add their CFG elements with their respective construction contexts.

Note that later when we visit these CXXBindTemporaryExprs during normal visit, we'd have to try to see if they form construction contexts for any of their children, which would mean that we'd try to create a construction context for the same constructor twice. This makes it a bit tricky to assert that the algorithm is working correctly; previously we could assert that the construction context is not being set twice. Now we make a weaker assertion, but still a powerful one: when we're trying to set the construction context twice, on our second attempt we should be having a construction context that is a sub-context of the context that we already have. In this case we keep the old context because it provides more informantion.

I also added a new assertion that says that all construction contexts were fully consumed when CFG is fully built.

A similar process is planned to be used for aggregate constructors, where the context may be identified via a chain of multiple InitListExprs (which may also contain multiple constructors).

Because the ConstructionContext class is becoming increasingly complex, i strongly believe i should split it up into sub-classes enumerated by kinds.

[NoQ]

Fix comment.

[dcoughlin]

It seems kind of sketchy to me that we're recursing over an expression to find construction contexts and then later doing it again for sub-expressions. I guess there is precedent here with VisitForTemporaryDtors(), but we should think about whether there is a better way to do this.

lib/Analysis/CFG.cpp

1160

This is kind of scary since it means we'll be recursing over subexpressions repeatedly. I guess VisitForTemporaryDtors() does this too, but it sounds like we're wasting a lot of computation visiting the subtrees over and over again.

include/clang/Analysis/CFG.h

 
 private:
   // The construction site - the statement that triggered the construction
   // for one of its parts. For instance, stack variable declaration statement
   // triggers construction of itself or its elements if it's an array,
   // new-expression triggers construction of the newly allocated object(s).
   TriggerTy Trigger;
 
-public:
+  // Sometimes a single trigger is not enough to describe the construction site.
+  // In this case we'd have a chain of "partial" construction contexts.
+  // Some examples:
+  // - A constructor within in an aggregate initializer list within a variable
+  //   would have a construction context of the initializer list with the parent
+  //   construction context of a variable.
+  // - A constructor for a temporary that needs to be both destroyed
+  //   and materialized into an elidable copy constructor would have a
+  //   construction context of a CXXBindTemporaryExpr with the parent
+  //   construction context of a MaterializeTemproraryExpr.
+  // Not all of these are currently supported.
+  const ConstructionContext *Parent = nullptr;
+
   ConstructionContext() = default;
-  ConstructionContext(TriggerTy Trigger)
-      : Trigger(Trigger) {}
+  ConstructionContext(TriggerTy Trigger, const ConstructionContext *Parent)
+      : Trigger(Trigger), Parent(Parent) {}
+
+public:
+  static const ConstructionContext *
+  create(BumpVectorContext &C, TriggerTy Trigger,
+         const ConstructionContext *Parent = nullptr) {
+    ConstructionContext *CC = C.getAllocator().Allocate<ConstructionContext>();
+    return new (CC) ConstructionContext(Trigger, Parent);
+  }
 
   bool isNull() const { return Trigger.isNull(); }
 
   TriggerTy getTrigger() const { return Trigger; }
+  const ConstructionContext *getParent() const { return Parent; }
 
   const Stmt *getTriggerStmt() const {
     return Trigger.dyn_cast<Stmt *>();
   }
 
   const CXXCtorInitializer *getTriggerInit() const {
     return Trigger.dyn_cast<CXXCtorInitializer *>();
   }
 
-  const ConstructionContext *getPersistentCopy(BumpVectorContext &C) const {
-    ConstructionContext *CC = C.getAllocator().Allocate<ConstructionContext>();
-    *CC = *this;
-    return CC;
+  bool isSameAsPartialContext(const ConstructionContext *Other) const {
+    assert(Other);
+    return (Trigger == Other->Trigger);
+  }
+
+  // See if Other is a proper initial segment of this construction context
+  // in terms of the parent chain - i.e. a few first parents coincide and
+  // then the other context terminates but our context goes further - i.e.,
+  // we are providing the same context that the other context provides,
+  // and a bit more above that.
+  bool isStrictlyMoreSpecificThan(const ConstructionContext *Other) const {
+    const ConstructionContext *Self = this;
+    while (true) {
+      if (!Other)
+        return Self;
+      if (!Self || !Self->isSameAsPartialContext(Other))
+        return false;
+      Self = Self->getParent();
+      Other = Other->getParent();
+    }
+    llvm_unreachable("The above loop can only be terminated via return!");
   }
 };
 
 /// CFGConstructor - Represents C++ constructor call. Maintains information
 /// necessary to figure out what memory is being initialized by the
 /// constructor expression. For now this is only used by the analyzer's CFG.
 class CFGConstructor : public CFGStmt {
 public:
public:
 
   /// Adds a (potentially unreachable) successor block to the current block.
   void addSuccessor(AdjacentBlock Succ, BumpVectorContext &C);
 
   void appendStmt(Stmt *statement, BumpVectorContext &C) {
     Elements.push_back(CFGStmt(statement), C);
   }
 
-  void appendConstructor(CXXConstructExpr *CE, const ConstructionContext &CC,
+  void appendConstructor(CXXConstructExpr *CE, const ConstructionContext *CC,
                          BumpVectorContext &C) {
-    Elements.push_back(CFGConstructor(CE, CC.getPersistentCopy(C)), C);
+    Elements.push_back(CFGConstructor(CE, CC), C);
   }
 
   void appendInitializer(CXXCtorInitializer *initializer,
                         BumpVectorContext &C) {
     Elements.push_back(CFGInitializer(initializer), C);
   }
 
   void appendNewAllocator(CXXNewExpr *NE,

lib/Analysis/CFG.cpp

class CFGBuilder {
 
   // A list of labels whose address has been taken (for indirect gotos).
   using LabelSetTy = llvm::SmallSetVector<LabelDecl *, 8>;
   LabelSetTy AddressTakenLabels;
 
   // Information about the currently visited C++ object construction site.
   // This is set in the construction trigger and read when the constructor
   // itself is being visited.
-  ConstructionContext CurrentConstructionContext = {};
+  llvm::DenseMap<CXXConstructExpr *, const ConstructionContext *>
+      ConstructionContextMap{};
 
   bool badCFG = false;
   const CFG::BuildOptions &BuildOpts;
   
   // State to track for building switch statements.
   bool switchExclusivelyCovered = false;
   Expr::EvalResult *switchCond = nullptr;
   
private:
   }
 
   // Scan the child statement \p Child to find the constructor that might
   // have been directly triggered by the current node, \p Trigger. If such
   // constructor has been found, set current construction context to point
   // to the trigger statement. The construction context will be unset once
   // it is consumed when the CFG building procedure processes the
   // construct-expression and adds the respective CFGConstructor element.
-  void EnterConstructionContextIfNecessary(
-      ConstructionContext::TriggerTy Trigger, Stmt *Child);
+  void findConstructionContexts(const ConstructionContext *ContextSoFar,
+                                Stmt *Child);
   // Unset the construction context after consuming it. This is done immediately
   // after adding the CFGConstructor element, so there's no need to
   // do this manually in every Visit... function.
-  void ExitConstructionContext();
+  void cleanupConstructionContext(CXXConstructExpr *CE);
 
   void autoCreateBlock() { if (!Block) Block = createBlock(); }
   CFGBlock *createBlock(bool add_successor = true);
   CFGBlock *createNoReturnBlock();
 
   CFGBlock *addStmt(Stmt *S) {
     return Visit(S, AddStmtChoice::AlwaysAdd);
   }
void appendStmt(CFGBlock *B, const Stmt *S) {
 
     // All block-level expressions should have already been IgnoreParens()ed.
     assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S);
     B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext());
   }
 
   void appendConstructor(CFGBlock *B, CXXConstructExpr *CE) {
     if (BuildOpts.AddRichCXXConstructors) {
-      if (!CurrentConstructionContext.isNull()) {
-        B->appendConstructor(CE, CurrentConstructionContext,
-                             cfg->getBumpVectorContext());
-        ExitConstructionContext();
+      if (const ConstructionContext *CC = ConstructionContextMap.lookup(CE)) {
+        B->appendConstructor(CE, CC, cfg->getBumpVectorContext());
+        cleanupConstructionContext(CE);
         return;
       }
     }
 
     // No valid construction context found. Fall back to statement.
     B->appendStmt(CE, cfg->getBumpVectorContext());
   }
 
if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt))
         return vat;
 
     t = vt->getElementType().getTypePtr();
   }
 
   return nullptr;
 }
 
-void CFGBuilder::EnterConstructionContextIfNecessary(
-    ConstructionContext::TriggerTy Trigger, Stmt *Child) {
+void CFGBuilder::findConstructionContexts(
+    const ConstructionContext *ContextSoFar, Stmt *Child) {
   if (!BuildOpts.AddRichCXXConstructors)
     return;
   if (!Child)
     return;
-  if (isa<CXXConstructExpr>(Child)) {
-    assert(CurrentConstructionContext.isNull() &&
-           "Already within a construction context!");
-    CurrentConstructionContext = ConstructionContext(Trigger);
+  if (auto *CE = dyn_cast<CXXConstructExpr>(Child)) {
+    if (const ConstructionContext *PreviousContext =
+            ConstructionContextMap.lookup(CE)) {
+      // We might have visited this child when we were finding construction
+      // contexts within its parents.
+      assert(PreviousContext->isStrictlyMoreSpecificThan(ContextSoFar) &&
+             "Already within a different construction context!");
+    } else {
+      ConstructionContextMap[CE] = ContextSoFar;
+    }
   } else if (auto *Cleanups = dyn_cast<ExprWithCleanups>(Child)) {
-    EnterConstructionContextIfNecessary(Trigger, Cleanups->getSubExpr());
+    findConstructionContexts(ContextSoFar, Cleanups->getSubExpr());
+  } else if (auto *BTE = dyn_cast<CXXBindTemporaryExpr>(Child)) {
+    findConstructionContexts(
+        ConstructionContext::create(cfg->getBumpVectorContext(), BTE,
+                                    ContextSoFar),
+        BTE->getSubExpr());
   }
 }
 
-void CFGBuilder::ExitConstructionContext() {
-  assert(!CurrentConstructionContext.isNull() &&
+void CFGBuilder::cleanupConstructionContext(CXXConstructExpr *CE) {
+  assert(BuildOpts.AddRichCXXConstructors &&
+         "We should not be managing construction contexts!");
+  assert(ConstructionContextMap.count(CE) &&
          "Cannot exit construction context without the context!");
-  CurrentConstructionContext = ConstructionContext();
+  ConstructionContextMap.erase(CE);
 }
 
 
 /// BuildCFG - Constructs a CFG from an AST (a Stmt*).  The AST can represent an
 ///  arbitrary statement.  Examples include a single expression or a function
 ///  body (compound statement).  The ownership of the returned CFG is
 ///  transferred to the caller.  If CFG construction fails, this method returns
 ///  NULL.
for (LabelSetTy::iterator I = AddressTakenLabels.begin(),
       if (LI == LabelMap.end()) continue;
       
       addSuccessor(B, LI->second.block);
     }
 
   // Create an empty entry block that has no predecessors.
   cfg->setEntry(createBlock());
 
+  if (BuildOpts.AddRichCXXConstructors)
+    assert(ConstructionContextMap.empty() &&
+           "Not all construction contexts were cleaned up!");
+
   return std::move(cfg);
 }
 
 /// createBlock - Used to lazily create blocks that are connected
 ///  to the current (global) succcessor.
 CFGBlock *CFGBuilder::createBlock(bool add_successor) {
   CFGBlock *B = cfg->createBlock();
   if (add_successor && Succ)
if (BuildOpts.AddTemporaryDtors && HasTemporaries) {
                              /*BindToTemporary=*/false, Context);
     }
   }
 
   autoCreateBlock();
   appendInitializer(Block, I);
 
   if (Init) {
-    EnterConstructionContextIfNecessary(I, Init);
+    findConstructionContexts(
+        ConstructionContext::create(cfg->getBumpVectorContext(), I),
+        Init);
 
     if (HasTemporaries) {
       // For expression with temporaries go directly to subexpression to omit
       // generating destructors for the second time.
       return Visit(cast<ExprWithCleanups>(Init)->getSubExpr());
     }
     if (BuildOpts.AddCXXDefaultInitExprInCtors) {
       if (CXXDefaultInitExpr *Default = dyn_cast<CXXDefaultInitExpr>(Init)) {
if (BuildOpts.AddTemporaryDtors && HasTemporaries) {
       VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
                              /*BindToTemporary=*/false, Context);
     }
   }
 
   autoCreateBlock();
   appendStmt(Block, DS);
 
-  EnterConstructionContextIfNecessary(DS, Init);
+  findConstructionContexts(
+      ConstructionContext::create(cfg->getBumpVectorContext(), DS),
+      Init);
 
   // Keep track of the last non-null block, as 'Block' can be nulled out
   // if the initializer expression is something like a 'while' in a
   // statement-expression.
   CFGBlock *LastBlock = Block;
 
   if (Init) {
     if (HasTemporaries) {
CFGBlock *CFGBuilder::VisitReturnStmt(ReturnStmt *R) {
   //       for that code; a simple "mark-and-sweep" from the entry block will be
   //       able to report such dead blocks.
 
   // Create the new block.
   Block = createBlock(false);
 
   addAutomaticObjHandling(ScopePos, LocalScope::const_iterator(), R);
 
-  EnterConstructionContextIfNecessary(R, R->getRetValue());
+  findConstructionContexts(
+      ConstructionContext::create(cfg->getBumpVectorContext(), R),
+      R->getRetValue());
 
   // If the one of the destructors does not return, we already have the Exit
   // block as a successor.
   if (!Block->hasNoReturnElement())
     addSuccessor(Block, &cfg->getExit());
 
   // Add the return statement to the block.  This may create new blocks if R
   // contains control-flow (short-circuit operations).

 }
 
 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
                                                 AddStmtChoice asc) {
   if (asc.alwaysAdd(*this, E)) {
     autoCreateBlock();
     appendStmt(Block, E);
 
-    EnterConstructionContextIfNecessary(E, E->getSubExpr());
+    findConstructionContexts(
+        ConstructionContext::create(cfg->getBumpVectorContext(), E),
+        E->getSubExpr());
 
     // We do not want to propagate the AlwaysAdd property.
     asc = asc.withAlwaysAdd(false);
   }
   return Visit(E->getSubExpr(), asc);
 }
 
 CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C,
                                             AddStmtChoice asc) {
   autoCreateBlock();
   appendConstructor(Block, C);
 
   return VisitChildren(C);
 }
 
 CFGBlock *CFGBuilder::VisitCXXNewExpr(CXXNewExpr *NE,
                                       AddStmtChoice asc) {
   autoCreateBlock();
   appendStmt(Block, NE);
 
-  EnterConstructionContextIfNecessary(
-      NE, const_cast<CXXConstructExpr *>(NE->getConstructExpr()));
+  findConstructionContexts(
+      ConstructionContext::create(cfg->getBumpVectorContext(), NE),
+      const_cast<CXXConstructExpr *>(NE->getConstructExpr()));
 
   if (NE->getInitializer())
     Block = Visit(NE->getInitializer());
 
   if (BuildOpts.AddCXXNewAllocator)
     appendNewAllocator(Block, NE);
 
   if (NE->isArray())