[clang-tidy] Sequence statements with multiple parents correctly (PR39149)

[mboehme]

Summary

Before this fix, the bugprone-use-after-move check could incorrectly
conclude that a use and move in a function template were not sequenced.
For details, see

https://bugs.llvm.org/show_bug.cgi?id=39149

[JonasToth]

clang-tidy/utils/ExprSequence.cpp

103 ↗

(On Diff #167946)

I find the first part of the comment unclear. Does this loop handle for only?

test/clang-tidy/bugprone-use-after-move.cpp

1198 ↗

(On Diff #167946)

Which other stmts? do they produce the same false positive?

[aaron.ballman]

clang-tidy/utils/ExprSequence.cpp

103 ↗

(On Diff #167946)

I think this means English "for" and not C for. Could rewrite to If a statement has multiple parents, instead.

[aaron.ballman]

This seems reasonable to me.

[mboehme]

• Responses to reviewer comments.

[mboehme]

clang-tidy/utils/ExprSequence.cpp

103 ↗

(On Diff #167946)

Yes, this is what I meant. Rephrased as Aaron suggested to remove the ambiguity.

test/clang-tidy/bugprone-use-after-move.cpp

1198 ↗

(On Diff #167946)

I've added the two other examples I'm aware of (continue and break statements) to the description. However, I haven't been able to use these to construct an example that triggers the false positive.

In general, any statement that TemplateInstantiator leaves unchanged will have multiple parents; I'm not sure which other statements this applies to. In my experience, any statement that contains an expression will be rebuilt, but I may be missing something here.

[JonasToth]

Thanks for clarification :)

[mboehme]

In D52782#1254933, @JonasToth wrote:

Thanks for clarification :)

Thanks! Do you agree this is ready to land now?

[JonasToth]

In D52782#1254945, @mboehme wrote:

In D52782#1254933, @JonasToth wrote:

Thanks for clarification :)

Thanks! Do you agree this is ready to land now?

Sure!

clang-tools-extra/trunk/clang-tidy/bugprone/UseAfterMoveCheck.cpp

bool UseAfterMoveFinder::find(Stmt *FunctionBody, const Expr *MovingCall,
   CFG::BuildOptions Options;
   Options.AddImplicitDtors = true;
   Options.AddTemporaryDtors = true;
   std::unique_ptr<CFG> TheCFG =
       CFG::buildCFG(nullptr, FunctionBody, Context, Options);
   if (!TheCFG)
     return false;
 
-  Sequence.reset(new ExprSequence(TheCFG.get(), Context));
-  BlockMap.reset(new StmtToBlockMap(TheCFG.get(), Context));
+  Sequence =
+      llvm::make_unique<ExprSequence>(TheCFG.get(), FunctionBody, Context);
+  BlockMap = llvm::make_unique<StmtToBlockMap>(TheCFG.get(), Context);
   Visited.clear();
 
   const CFGBlock *Block = BlockMap->blockContainingStmt(MovingCall);
   if (!Block)
     return false;
 
   return findInternal(Block, MovingCall, MovedVariable, TheUseAfterMove);
 }

clang-tools-extra/trunk/clang-tidy/utils/ExprSequence.h

 ///
 /// - In addition, some `Stmt`s are known to be sequenced before or after
 ///   their siblings. For example, the `Stmt`s that make up a `CompoundStmt`are
 ///   all sequenced relative to each other. The function
 ///   `getSequenceSuccessor()` implements these sequencing rules.
 class ExprSequence {
 public:
   /// Initializes this `ExprSequence` with sequence information for the given
-  /// `CFG`.
-  ExprSequence(const CFG *TheCFG, ASTContext *TheContext);
+  /// `CFG`. `Root` is the root statement the CFG was built from.
+  ExprSequence(const CFG *TheCFG, const Stmt *Root, ASTContext *TheContext);
 
   /// Returns whether \p Before is sequenced before \p After.
   bool inSequence(const Stmt *Before, const Stmt *After) const;
 
   /// Returns whether \p After can potentially be evaluated after \p Before.
   /// This is exactly equivalent to `!inSequence(After, Before)` but makes some
   /// conditions read more naturally.
   bool potentiallyAfter(const Stmt *After, const Stmt *Before) const;
 
 private:
   // Returns the sibling of \p S (if any) that is directly sequenced after \p S,
   // or nullptr if no such sibling exists. For example, if \p S is the child of
   // a `CompoundStmt`, this would return the Stmt that directly follows \p S in
   // the `CompoundStmt`.
   //
   // As the sequencing of many constructs that change control flow is already
   // encoded in the `CFG`, this function only implements the sequencing rules
   // for those constructs where sequencing cannot be inferred from the `CFG`.
   const Stmt *getSequenceSuccessor(const Stmt *S) const;
 
   const Stmt *resolveSyntheticStmt(const Stmt *S) const;
 
   ASTContext *Context;
+  const Stmt *Root;
 
   llvm::DenseMap<const Stmt *, const Stmt *> SyntheticStmtSourceMap;
 };
 
 /// Maps `Stmt`s to the `CFGBlock` that contains them. Some `Stmt`s may be
 /// contained in more than one `CFGBlock`; in this case, they are mapped to the
 /// innermost block (i.e. the one that is furthest from the root of the tree).
 class StmtToBlockMap {

clang-tools-extra/trunk/clang-tidy/utils/ExprSequence.cpp

for (const Stmt *Parent : getParentStmts(Descendant, Context)) {
     if (isDescendantOrEqual(Parent, Ancestor, Context))
       return true;
   }
 
   return false;
 }
 }
 
-ExprSequence::ExprSequence(const CFG *TheCFG, ASTContext *TheContext)
-    : Context(TheContext) {
+ExprSequence::ExprSequence(const CFG *TheCFG, const Stmt *Root,
+                           ASTContext *TheContext)
+    : Context(TheContext), Root(Root) {
   for (const auto &SyntheticStmt : TheCFG->synthetic_stmts()) {
     SyntheticStmtSourceMap[SyntheticStmt.first] = SyntheticStmt.second;
   }
 }
 
 bool ExprSequence::inSequence(const Stmt *Before, const Stmt *After) const {
   Before = resolveSyntheticStmt(Before);
   After = resolveSyntheticStmt(After);

 
 bool ExprSequence::potentiallyAfter(const Stmt *After,
                                     const Stmt *Before) const {
   return !inSequence(After, Before);
 }
 
 const Stmt *ExprSequence::getSequenceSuccessor(const Stmt *S) const {
   for (const Stmt *Parent : getParentStmts(S, Context)) {
+    // If a statement has multiple parents, make sure we're using the parent
+    // that lies within the sub-tree under Root.
+    if (!isDescendantOrEqual(Parent, Root, Context))
+      continue;
+
     if (const auto *BO = dyn_cast<BinaryOperator>(Parent)) {
       // Comma operator: Right-hand side is sequenced after the left-hand side.
       if (BO->getLHS() == S && BO->getOpcode() == BO_Comma)
         return BO->getRHS();
     } else if (const auto *InitList = dyn_cast<InitListExpr>(Parent)) {
       // Initializer list: Each initializer clause is sequenced after the
       // clauses that precede it.
       for (unsigned I = 1; I < InitList->getNumInits(); ++I) {

clang-tools-extra/trunk/test/clang-tidy/bugprone-use-after-move.cpp

for (int i = 0; i < 10; ++i) {
     A a1;
     switch (A a2 = a1; A a3 = std::move(a2)) {
       case true:
         std::move(a3);
     }
   }
 }
 
+// Some statements in templates (e.g. null, break and continue statements) may
+// be shared between the uninstantiated and instantiated versions of the
+// template and therefore have multiple parents. Make sure the sequencing code
+// handles this correctly.
+template <class> void nullStatementSequencesInTemplate() {
+  int c = 0;
+  (void)c;
+  ;
+  std::move(c);
+}
+template void nullStatementSequencesInTemplate<int>();
+
 namespace PR33020 {
 class D {
   ~D();
 };
 struct A {
   D d;
 };
 class B {