[Sema] SequenceChecker: Fix handling of operator ||, && and ?:

[riccibruno]

Summary

The current handling of the operators ||, && and ?: has a number of false positive and false negative. The issues for operator || and && are:

1. We need to add sequencing regions for the LHS and RHS as is done for the comma operator. Not doing so causes false positives in expressions like ((a++, false) || (a++, false)); (from PR39779, see PR22197 for another example).

2. In the current implementation when the evaluation of the LHS fails, the RHS is added to a worklist to be processed later. This results in false negatives in expressions like (a && a++) + a.

Fix these issues by introducing sequencing regions for the LHS and RHS, and by not deferring the visitation of the RHS.

The issues with the ternary operator ?: are similar, with the added twist that we should not warn on expressions like (x ? y += 1 : y += 2) since exactly one of the 2nd and 3rd expression is going to be evaluated, but we should still warn on expressions like (x ? y += 1 : y += 2) = y.

[riccibruno]

Looking at git blame, this change means that we will warn on (b && x++) + (!b && x++). However we will also warn on an expression like (x > some_constant && y++) + (x < some_constant && y++). This seems to be the job of a static analyser which is able to do some control flow analysis. Moreover for this warning it seems to me that having some false negatives is worse than having some false positive. As a data point I ran this on the entire LLVM codebase and on all of Boost, and did not find any additional warning.

[rsmith]

The "false negatives" in the current behaviour are the result of an intentional decision to avoid false positives for unsequenced operations that cannot actually both happen as part of the same evaluation (because both are conditional on different and mutually-exclusive conditions), such as the false positive we now get in the tests. I think it's reasonable to revisit that decision, though; the new false positive cases do not realistically seem likely to occur in real code whereas the false negatives do.

test/Sema/warn-unsequenced.c

79–80

Please at least add a FIXME for this false positive.

[riccibruno]

Rebased

[riccibruno]

Rebased on D57660. No need to look at it.

[riccibruno]

Rebased

[xbolva00]

Does the whole stack of patch need to be commited at once or maybe you can land them individually?

[riccibruno]

In D57747#1774848, @xbolva00 wrote:

Does the whole stack of patch need to be commited at once or maybe you can land them individually?

Hi, thanks for looking at this patch series !

If I remember correctly (it has been a while now) these patches could be landed independently. I was sort of hoping that D57660 would get accepted and that I could then land the other patches without rebasing them (the tests are especially annoying to rebase). That said if D57660 is a problem then I can totally do the work and land the other already accepted patches.

[riccibruno]

Rebased on top of current master and D57659. No need to look at it.

lib/Sema/SemaChecking.cpp

checkUsage(MemoryLoc, UI, ModExpr, /*OtherKind=*/UK_ModAsSideEffect,
                /*IsModMod=*/true);
     addUsage(MemoryLoc, UI, ModExpr, /*UsageKind=*/UK);
   }
 
 public:
   SequenceChecker(Sema &S, Expr *E, SmallVectorImpl<Expr *> &WorkList)
       : Base(S.Context), SemaRef(S), Region(Tree.root()), WorkList(WorkList) {
     Visit(E);
+    // Silence a -Wunused-private-field since WorkList is now unused.
+    // TODO: Evaluate if it can be used, and if not remove it.
+    (void)this->WorkList;
   }
 
   void VisitStmt(Stmt *S) {
     // Skip all statements which aren't expressions for now.
   }
 
   void VisitExpr(Expr *E) {
     // By default, just recurse to evaluated subexpressions.
void VisitUnaryPostIncDec(UnaryOperator *UO) {
     if (!MemoryLoc)
       return VisitExpr(UO);
 
     notePreMod(MemoryLoc, UO);
     Visit(UO->getSubExpr());
     notePostMod(MemoryLoc, UO, UK_ModAsSideEffect);
   }
 
-  /// Don't visit the RHS of '&&' or '||' if it might not be evaluated.
   void VisitBinLOr(BinaryOperator *BO) {
-    // The side-effects of the LHS of an '&&' are sequenced before the
-    // value computation of the RHS, and hence before the value computation
-    // of the '&&' itself, unless the LHS evaluates to zero. We treat them
-    // as if they were unconditionally sequenced.
+    // C++11 [expr.log.or]p2:
+    //  If the second expression is evaluated, every value computation and
+    //  side effect associated with the first expression is sequenced before
+    //  every value computation and side effect associated with the
+    //  second expression.
+    SequenceTree::Seq LHSRegion = Tree.allocate(Region);
+    SequenceTree::Seq RHSRegion = Tree.allocate(Region);
+    SequenceTree::Seq OldRegion = Region;
+
     EvaluationTracker Eval(*this);
     {
       SequencedSubexpression Sequenced(*this);
+      Region = LHSRegion;
       Visit(BO->getLHS());
     }
 
-    bool Result;
-    if (Eval.evaluate(BO->getLHS(), Result)) {
-      if (!Result)
-        Visit(BO->getRHS());
-    } else {
-      // Check for unsequenced operations in the RHS, treating it as an
-      // entirely separate evaluation.
-      //
-      // FIXME: If there are operations in the RHS which are unsequenced
-      // with respect to operations outside the RHS, and those operations
-      // are unconditionally evaluated, diagnose them.
-      WorkList.push_back(BO->getRHS());
+    // C++11 [expr.log.or]p1:
+    //  [...] the second operand is not evaluated if the first operand
+    //  evaluates to true.
+    bool EvalResult = false;
+    bool EvalOK = Eval.evaluate(BO->getLHS(), EvalResult);
+    bool ShouldVisitRHS = !EvalOK || (EvalOK && !EvalResult);
+    if (ShouldVisitRHS) {
+      Region = RHSRegion;
     }
+
+    Region = OldRegion;
+    Tree.merge(LHSRegion);
+    Tree.merge(RHSRegion);
   }
   void VisitBinLAnd(BinaryOperator *BO) {
+    // C++11 [expr.log.and]p2:
+    //  If the second expression is evaluated, every value computation and
+    //  side effect associated with the first expression is sequenced before
+    //  every value computation and side effect associated with the
+    //  second expression.
+    SequenceTree::Seq LHSRegion = Tree.allocate(Region);
+    SequenceTree::Seq RHSRegion = Tree.allocate(Region);
+    SequenceTree::Seq OldRegion = Region;
+
     EvaluationTracker Eval(*this);
     {
       SequencedSubexpression Sequenced(*this);
+      Region = LHSRegion;
       Visit(BO->getLHS());
     }
 
-    bool Result;
-    if (Eval.evaluate(BO->getLHS(), Result)) {
-      if (Result)
-        Visit(BO->getRHS());
-    } else {
-      WorkList.push_back(BO->getRHS());
+    // C++11 [expr.log.and]p1:
+    //  [...] the second operand is not evaluated if the first operand is false.
+    bool EvalResult = false;
+    bool EvalOK = Eval.evaluate(BO->getLHS(), EvalResult);
+    bool ShouldVisitRHS = !EvalOK || (EvalOK && EvalResult);
+    if (ShouldVisitRHS) {
+      Region = RHSRegion;
     }
+
+    Region = OldRegion;
+    Tree.merge(LHSRegion);
+    Tree.merge(RHSRegion);
   }
 
-  // Only visit the condition, unless we can be sure which subexpression will
-  // be chosen.
   void VisitAbstractConditionalOperator(AbstractConditionalOperator *CO) {
+    // C++11 [expr.cond]p1:
+    //  [...] Every value computation and side effect associated with the first
+    //  expression is sequenced before every value computation and side effect
+    //  associated with the second or third expression.
+    SequenceTree::Seq ConditionRegion = Tree.allocate(Region);
+    // No sequencing is specified between the true and false expression.
+    // However since exactly one of both is going to be evaluated we can
+    // consider them to be sequenced. This is needed to avoid warning on
+    // something like "x ? y+= 1 : y += 2;" in the case where we will visit
+    // both the true and false expressions because we can't evaluate x.
+    // This will still allow us to detect an expression like (pre C++17)
+    // "(x ? y += 1 : y += 2) = y".
+    //
+    // We don't wrap the visitation of the true and false expression with
+    // SequencedSubexpression because we don't want to downgrade modifications
+    // as side effect in the true and false expressions after the visition
+    // is done. (for example in the expression "(x ? y++ : y++) + y" we should
+    // not warn between the two "y++", but we should warn between the "y++"
+    // and the "y".
+    SequenceTree::Seq TrueRegion = Tree.allocate(Region);
+    SequenceTree::Seq FalseRegion = Tree.allocate(Region);
+    SequenceTree::Seq OldRegion = Region;
+
     EvaluationTracker Eval(*this);
     {
       SequencedSubexpression Sequenced(*this);
+      Region = ConditionRegion;
       Visit(CO->getCond());
     }
 
-    bool Result;
-    if (Eval.evaluate(CO->getCond(), Result))
-      Visit(Result ? CO->getTrueExpr() : CO->getFalseExpr());
-    else {
-      WorkList.push_back(CO->getTrueExpr());
-      WorkList.push_back(CO->getFalseExpr());
+    // C++11 [expr.cond]p1:
+    // [...] The first expression is contextually converted to bool (Clause 4).
+    // It is evaluated and if it is true, the result of the conditional
+    // expression is the value of the second expression, otherwise that of the
+    // third expression. Only one of the second and third expressions is
+    // evaluated. [...]
+    bool EvalResult = false;
+    bool EvalOK = Eval.evaluate(CO->getCond(), EvalResult);
+    bool ShouldVisitTrueExpr = !EvalOK || (EvalOK && EvalResult);
+    bool ShouldVisitFalseExpr = !EvalOK || (EvalOK && !EvalResult);
+    if (ShouldVisitTrueExpr) {
+      Region = TrueRegion;
+      Visit(CO->getTrueExpr());
+    }
+    if (ShouldVisitFalseExpr) {
+      Region = FalseRegion;
+      Visit(CO->getFalseExpr());
     }
+
+    Region = OldRegion;
+    Tree.merge(ConditionRegion);
+    Tree.merge(TrueRegion);
+    Tree.merge(FalseRegion);
   }
 
   void VisitCallExpr(CallExpr *CE) {
     // C++11 [intro.execution]p15:
     //   When calling a function [...], every value computation and side effect
     //   associated with any argument expression, or with the postfix expression
     //   designating the called function, is sequenced before execution of every
     //   expression or statement in the body of the function [and thus before

test/Sema/warn-unsequenced.c

void test() {
   f(a++, 0) + a++; // expected-warning {{multiple unsequenced modifications}}
 
   a = ++a; // expected-warning {{multiple unsequenced modifications}}
   a += ++a; // expected-warning {{unsequenced modification and access}}
 
   A agg1 = { a++, a++ }; // expected-warning {{multiple unsequenced modifications}}
   A agg2 = { a++ + a, a++ }; // expected-warning {{unsequenced modification and access}}
 
-  (xs[2] && (a = 0)) + a; // ok
+  (xs[2] && (a = 0)) + a; // expected-warning {{unsequenced modification and access to 'a'}}
   (0 && (a = 0)) + a; // ok
   (1 && (a = 0)) + a; // expected-warning {{unsequenced modification and access}}
 
-  (xs[3] || (a = 0)) + a; // ok
+  (xs[3] || (a = 0)) + a; // expected-warning {{unsequenced modification and access to 'a'}}
   (0 || (a = 0)) + a; // expected-warning {{unsequenced modification and access}}
   (1 || (a = 0)) + a; // ok
 
-  (xs[4] ? a : ++a) + a; // ok
+  (xs[4] ? a : ++a) + a; // expected-warning {{unsequenced modification and access to 'a'}}
   (0 ? a : ++a) + a; // expected-warning {{unsequenced modification and access}}
   (1 ? a : ++a) + a; // ok
-  (xs[5] ? ++a : ++a) + a; // FIXME: warn here
+  (xs[5] ? ++a : ++a) + a; // expected-warning {{unsequenced modification and access to 'a'}}
 
   (++a, xs[6] ? ++a : 0) + a; // expected-warning {{unsequenced modification and access}}
 
   // Here, the read of the fourth 'a' might happen before or after the write to
   // the second 'a'.
   a += (a++, a) + a; // expected-warning {{unsequenced modification and access}}
 
   int *p = xs;
   a = *(a++, p); // ok
   a = a++ && a; // ok
 
   A *q = &agg1;
   (q = &agg2)->y = q->x; // expected-warning {{unsequenced modification and access to 'q'}}
 
   // This has undefined behavior if a == 0; otherwise, the side-effect of the
   // increment is sequenced before the value computation of 'f(a, a)', which is
   // sequenced before the value computation of the '&&', which is sequenced
   // before the assignment. We treat the sequencing in '&&' as being
   // unconditional.
   a = a++ && f(a, a);
 
-  // This has undefined behavior if a != 0. FIXME: We should diagnose this.
-  (a && a++) + a;
+  // This has undefined behavior if a != 0.
+  (a && a++) + a; // expected-warning {{unsequenced modification and access to 'a'}}
 
-  (xs[7] && ++a) * (!xs[7] && ++a); // ok
+  // FIXME: Find a way to avoid warning here.
+  (xs[7] && ++a) * (!xs[7] && ++a); // expected-warning {{multiple unsequenced modifications to 'a'}}
 
   xs[0] = (a = 1, a); // ok
 
   xs[8] ? ++a + a++ : 0; // expected-warning {{multiple unsequenced modifications}}
   xs[8] ? 0 : ++a + a++; // expected-warning {{multiple unsequenced modifications}}
   xs[8] ? ++a : a++; // ok
 
   xs[8] && (++a + a++); // expected-warning {{multiple unsequenced modifications}}

test/SemaCXX/warn-unsequenced.cpp

 // RUN: %clang_cc1 -fsyntax-only -verify=cxx11 -std=c++11 -Wno-unused -Wno-uninitialized -Wunsequenced %s
 // RUN: %clang_cc1 -fsyntax-only -verify=cxx17 -std=c++17 -Wno-unused -Wno-uninitialized -Wunsequenced %s
 
 int f(int, int = 0);
+int g1();
+int g2(int);
 
 struct A {
   int x, y;
 };
 struct S {
   S(int, int);
   int n;
 };
void test() {
   struct Z { A a; S s; } z = { { ++a, ++a }, { ++a, ++a } }; // ok
   a = S { ++a, a++ }.n; // ok
   A { ++a, a++ }.x; // ok
   a = A { ++a, a++ }.x; // cxx11-warning {{multiple unsequenced modifications to 'a'}}
                         // TODO cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
   A { ++a, a++ }.x + A { ++a, a++ }.y; // cxx11-warning {{multiple unsequenced modifications to 'a'}}
                                        // cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
 
-  (xs[2] && (a = 0)) + a; // ok
+  (xs[2] && (a = 0)) + a; // cxx11-warning {{unsequenced modification and access to 'a'}}
+                          // cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
   (0 && (a = 0)) + a; // ok
   (1 && (a = 0)) + a; // cxx11-warning {{unsequenced modification and access to 'a'}}
                       // cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
 
-  (xs[3] || (a = 0)) + a; // ok
+  (xs[3] || (a = 0)) + a; // cxx11-warning {{unsequenced modification and access to 'a'}}
+                          // cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
   (0 || (a = 0)) + a; // cxx11-warning {{unsequenced modification and access to 'a'}}
                       // cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
   (1 || (a = 0)) + a; // ok
 
-  (xs[4] ? a : ++a) + a; // ok
+  (xs[4] ? a : ++a) + a; // cxx11-warning {{unsequenced modification and access to 'a'}}
+                         // cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
   (0 ? a : ++a) + a; // cxx11-warning {{unsequenced modification and access to 'a'}}
                      // cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
   (1 ? a : ++a) + a; // ok
   (0 ? a : a++) + a; // cxx11-warning {{unsequenced modification and access to 'a'}}
                      // cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
   (1 ? a : a++) + a; // ok
-  (xs[5] ? ++a : ++a) + a; // FIXME: warn here
+  (xs[5] ? ++a : ++a) + a; // cxx11-warning {{unsequenced modification and access to 'a'}}
+                           // cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
 
   (++a, xs[6] ? ++a : 0) + a; // cxx11-warning {{unsequenced modification and access to 'a'}}
                               // cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
 
   // Here, the read of the fourth 'a' might happen before or after the write to
   // the second 'a'.
   a += (a++, a) + a; // cxx11-warning {{unsequenced modification and access to 'a'}}
                      // cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
void test() {
 
   // This has undefined behavior if a == 0; otherwise, the side-effect of the
   // increment is sequenced before the value computation of 'f(a, a)', which is
   // sequenced before the value computation of the '&&', which is sequenced
   // before the assignment. We treat the sequencing in '&&' as being
   // unconditional.
   a = a++ && f(a, a);
 
-  // This has undefined behavior if a != 0. FIXME: We should diagnose this.
-  (a && a++) + a;
+  // This has undefined behavior if a != 0.
+  (a && a++) + a; // cxx11-warning {{unsequenced modification and access to 'a'}}
+                  // cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
 
-  (xs[7] && ++a) * (!xs[7] && ++a); // ok
+  // FIXME: Don't warn here.
+  (xs[7] && ++a) * (!xs[7] && ++a); // cxx11-warning {{multiple unsequenced modifications to 'a'}}
+                                    // cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
 
   xs[0] = (a = 1, a); // ok
   (a -= 128) &= 128; // ok
   ++a += 1; // ok
 
   xs[8] ? ++a + a++ : 0; // cxx11-warning {{multiple unsequenced modifications to 'a'}}
                          // cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
   xs[8] ? 0 : ++a + a++; // cxx11-warning {{multiple unsequenced modifications to 'a'}}
                          // cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
-  xs[8] ? ++a : a++; // ok
+  xs[8] ? ++a : a++; // no-warning
+  xs[8] ? a+=1 : a+= 2; // no-warning
+  (xs[8] ? a+=1 : a+= 2) = a; // cxx11-warning {{unsequenced modification and access to 'a'}}
+                              // TODO cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
+  (xs[8] ? a+=1 : a) = a; // cxx11-warning {{unsequenced modification and access to 'a'}}
+                          // TODO cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
+  (xs[8] ? a : a+= 2) = a; // cxx11-warning {{unsequenced modification and access to 'a'}}
+                           // TODO cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
+  a = (xs[8] ? a+=1 : a+= 2); // no-warning
+  a += (xs[8] ? a+=1 : a+= 2); // cxx11-warning {{unsequenced modification and access to 'a'}}
+                               // TODO cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
+
+  (false ? a+=1 : a) = a; // no-warning
+  (true ? a+=1 : a) = a; // cxx11-warning {{unsequenced modification and access to 'a'}}
+                         // TODO cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
+  (false ? a : a+=2) = a; // cxx11-warning {{unsequenced modification and access to 'a'}}
+                          // TODO cxx17-warning@-1 {{unsequenced modification and access to 'a'}}
+  (true ? a : a+=2) = a; // no-warning
 
   xs[8] && (++a + a++); // cxx11-warning {{multiple unsequenced modifications to 'a'}}
                         // cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
   xs[8] || (++a + a++); // cxx11-warning {{multiple unsequenced modifications to 'a'}}
                         // cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
 
+  ((a++, false) || (a++, false)); // no-warning PR39779
+  ((a++, true) && (a++, true)); // no-warning PR39779
+
+  int i,j;
+  (i = g1(), false) || (j = g2(i)); // no-warning PR22197
+  (i = g1(), true) && (j = g2(i)); // no-warning PR22197
+
+  (a++, false) || (a++, false) || (a++, false) || (a++, false); // no-warning
+  (a++, true) || (a++, true) || (a++, true) || (a++, true); // no-warning
+  a = ((a++, false) || (a++, false) || (a++, false) || (a++, false)); // no-warning
+  a = ((a++, true) && (a++, true) && (a++, true) && (a++, true)); // no-warning
+  a = ((a++, false) || (a++, false) || (a++, false) || a++); // cxx11-warning {{multiple unsequenced modifications to 'a'}}
+                                                             // TODO cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
+  a = ((a++, true) && (a++, true) && (a++, true) && a++); // cxx11-warning {{multiple unsequenced modifications to 'a'}}
+                                                          // TODO cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
+  a = ((a++, false) || (a++, false) || (a++, false) || (a + a, false)); // no-warning
+  a = ((a++, true) && (a++, true) && (a++, true) && (a + a, true)); // no-warning
+
+  a = (false && a++); // no-warning
+  a = (true && a++); // cxx11-warning {{multiple unsequenced modifications to 'a'}}
+                     // TODO cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
+  a = (true && ++a); // no-warning
+  a = (true || a++); // no-warning
+  a = (false || a++); // cxx11-warning {{multiple unsequenced modifications to 'a'}}
+                      // TODO cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
+  a = (false || ++a); // no-warning
+
+  (a++) | (a++); // cxx11-warning {{multiple unsequenced modifications to 'a'}}
+                 // cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
+  (a++) & (a++); // cxx11-warning {{multiple unsequenced modifications to 'a'}}
+                 // cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
+  (a++) ^ (a++); // cxx11-warning {{multiple unsequenced modifications to 'a'}}
+                 // cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
+
   (__builtin_classify_type(++a) ? 1 : 0) + ++a; // ok
   (__builtin_constant_p(++a) ? 1 : 0) + ++a; // ok
   (__builtin_object_size(&(++a, a), 0) ? 1 : 0) + ++a; // ok
   (__builtin_expect(++a, 0) ? 1 : 0) + ++a; // cxx11-warning {{multiple unsequenced modifications to 'a'}}
                                             // cxx17-warning@-1 {{multiple unsequenced modifications to 'a'}}
 }
 
 namespace members {