[Sema] Fix -Warray-bounds false negative when casting an out-of-bounds array item

[ilya]

Summary

Patch by Ilya Mirsky!

Fixes: http://llvm.org/PR44343

[riccibruno]

These are not the only AST nodes representing cast expressions (there is also CXXFunctionalCastExpr, ...). What about replacing the IgnoreParenImpCasts() above by IgnoreParenCasts() ? Incidentally doing this uncovers another test (Parser/cxx-ambig-decl-expr.cpp ) where this diagnostic is triggered.

[rsmith]

In addition to @riccibruno's comment, I found a couple of other suspicious things nearby (unrelated to the fix in this patch). No need to address them in this patch unless you feel motivated :)

clang/lib/Sema/SemaChecking.cpp

14389–14390

Hmm, don't we need to do different things for dot and arrow in this case?

14389–14390

Doesn't this need to preserve the AllowOnePastEnd value to avoid a false positive for &(cond ? arr1[N] : arr2[N])?

[efriedma]

To be rigorous, we should perform "pointer" checking for every operation that performs pointer arithmetic. Then we should perform "lvalue" checking (which doesn't allow pointers one past the end) in the following places:

1. When we take the address of an lvalue.
2. When we form a reference to an lvalue.
3. When we perform an lvalue-to-rvalue conversion.
4. When we perform an assignment to an lvalue.

This sort of piecemeal approach of recursively looking through arbitrary expressions seems likely to miss cases. For example, we currently don't perform checks inside compound literals.

[rsmith]

In D71714#1792085, @efriedma wrote:

To be rigorous, we should perform "pointer" checking for every operation that performs pointer arithmetic. Then we should perform "lvalue" checking (which doesn't allow pointers one past the end) in the following places:

1. When we take the address of an lvalue.
2. When we form a reference to an lvalue.
3. When we perform an lvalue-to-rvalue conversion.
4. When we perform an assignment to an lvalue.

This sort of piecemeal approach of recursively looking through arbitrary expressions seems likely to miss cases. For example, we currently don't perform checks inside compound literals.

I agree that this approach is not good. I'm concerned that your direction might still miss things, though (and it seems to involve a lot of AST traversal, which would be nice to avoid). For example, __builtin_bitcast performs a load without an lvalue-to-rvalue conversion, and to be thorough we'd need to special-case it. Perhaps we could instead:

• warn immediately when indexing outside [0, N] inclusive
• produce a deferred warning when indexing with index N, and diagnose at the end of the expression evaluation context
• remove elements from the list of deferred warnings when handling an & operator

In C at least, that should be correct in all cases. I think it's correct in C++ as well; there are lots more forms of lvalue to walk into in the third step (eg, &(cond ? x[n] : y[n]) shouldn't warn), but it seems feasible to enumerate. (This would lose the warnings on *&x[n], but I don't think that's a disaster.)

[efriedma]

and it seems to involve a lot of AST traversal

I was thinking we'd just call into SemaChecking in appropriate places. I guess there's a little AST traversal to figure whether an expression forms an array address. Your idea seems simpler.

remove elements from the list of deferred warnings when handling an & operator

For C++, I think you might also need to handle discarded-value expressions? Maybe it's okay if we warn anyway in that case. :)

This would lose the warnings on *&x[n], but I don't think that's a disaster

And more generally *(x+n), although I guess that isn't implemented now anyway.

[ilya]

In D71714#1791464, @riccibruno wrote:

These are not the only AST nodes representing cast expressions (there is also CXXFunctionalCastExpr, ...). What about replacing the IgnoreParenImpCasts() above by IgnoreParenCasts() ? Incidentally doing this uncovers another test (Parser/cxx-ambig-decl-expr.cpp ) where this diagnostic is triggered.

Thanks, using IgnoreParenCasts is even better.

clang/lib/Sema/SemaChecking.cpp

14389–14390

There are several test cases for an out of bounds access on an array member using dot and arrow operators in array-bounds.cpp. Do you have a specific test case for which you think the code is broken?

[ilya]

1. Refactor CheckArrayAccess() to take AllowPastTheEnd parameter to avoid a false positive array out-of-bounds warning for &(cond ? arr1[N] : arr2[N]).
2. Use IgnoreParenCasts() instead of IgnoreParenImpCasts() in CheckArrayAccess() to avoid false negatives when explicit cast is involved.

[ilya]

Implemented @riccibruno's and @rsmith's comments.
While I agree with the general notion about the flaws with the current implementation, I feel that the more major refactoring proposed in this review is out of the scope of this minor fix.

[ilya]

Kind ping

[rsmith]

clang/lib/Sema/SemaChecking.cpp

14389–14390

There are several test cases for an out of bounds access on an array member using dot and arrow operators in array-bounds.cpp. Do you have a specific test case for which you think the code is broken?

Sure. There's a false negative for this:

struct A { int n; };
A *a[4];
int *n = &a[4]->n;

... because we incorrectly visit the left-hand side of the -> with AllowOnePastEnd == 1. The left-hand side of -> is subject to lvalue-to-rvalue conversion, so can't be one-past-the-end regardless of the context in which the -> appears.

clang/test/SemaCXX/array-bounds.cpp

331

This case should warn; dynamic_cast will access the object's vptr. Please at least add a FIXME.

[rsmith]

In D71714#1795313, @ilya wrote:

While I agree with the general notion about the flaws with the current implementation, I feel that the more major refactoring proposed in this review is out of the scope of this minor fix.

I'm OK with making the minor fix here and deferring the larger rework.

[ilya]

Address rsmith's comments.

[ilya]

clang/lib/Sema/SemaChecking.cpp

14389–14390

... because we incorrectly visit the left-hand side of the -> with AllowOnePastEnd == 1. The left-hand side of -> is subject to lvalue-to-rvalue conversion, so can't be one-past-the-end regardless of the context in which the -> appears.

Thanks for clarifying. So basically we don't want to allow one-past-end for MemberExpr?

[ebevhan]

clang/lib/Sema/SemaChecking.cpp

14389–14390

Thanks for clarifying. So basically we don't want to allow one-past-end for MemberExpr?

I think the point is rather that when the MemberExpr isArrow, we want to think of it as performing an implicit dereference first, and thus we should do AllowOnePastEnd-- before recursing if that is the case.

[ilya]

clang/lib/Sema/SemaChecking.cpp

14389–14390

I think the point is rather that when the MemberExpr isArrow, we want to think of it as performing an implicit dereference first, and thus we should do AllowOnePastEnd-- before recursing if that is the case.

@ebevhan and I have discussed this offline, and we believe that there's no reason to allow an address-of of a member of a one past-the-end value, using either '.' or '->' operators, regardless of the fact that referencing a member of a one past-the-end value using '.' is merely a pointer arithmetic and doesn't imply dereferencing, as with operator '->'.

We couldn't find any reference in the C++ 2017 N4659 regarding member access of a one past-the-end value. Only mentions of one past-the-end in the context of iterators (27.2.1 p. 7) and pointer arithmetic (8.3.1 p. 3).

ISO C99 describes in 6.5.3.2 p. 3 that if the operand to the '&' operator is the result of an unary '*' operator (or array subscript, implictly), the two operators "cancel" each other, but it says nothing about the case when there's a member expression "in-between", (the member expression section, 6.5.2.3, says nothing about that either).

@rsmith, what do you think?

[ilya]

Ping

[ilya]

One last kind ping

[vabridgers]

Ping @rsmith . Are you ok if I rebase and push this change? Or do you have specific items that require attention? I've spoken to @ilya , he's ok if I clean this up and push with credit to him. Thanks

[vabridgers]

Rebase, commandeer this patch from Ilya.

[vabridgers]

Ping. Could someone pick up review of this patch again, please? Ilya left off with a question to @rsmith , and at that point all activity fell off. Thanks.

[vabridgers]

Gentle and polite ping :) Could someone have a look at this? @rsmith , or @lattner ? Thanks.

[rsmith]

clang/lib/Sema/SemaChecking.cpp

14389–14390

Let's give this a go. I'm a little concerned that people might write things like:

struct X { int n; };
X x[32];
int *end = &x[32].n;

I don't think that has defined behavior in C++, because there isn't an X object so there isn't an n member to refer to, but I think it's probably OK in C (hard to say in both cases, though, due to underspecification in both standards). Nonetheless, such code is at least questionable. I don't think we have a good way to determine how well this warning will work other than trying it, so let's do that.

Please be prepared to revert and do something more conservative if we find this fires a lot on somewhat-reasonable code :)

[vabridgers]

Thanks @rsmith, will do. Best!

[thakis]

Hi,

this causes a warning in harfbuzz on code that looks like so:

UChar decomposed[4];
...
int len = unorm2_getRawDecomposition(...decomposed, ARRAY_LENGTH (decomposed)...)
if (len == 1) {
  U16_GET_UNSAFE (decomposed, 0, *a);

where U16_GET_UNSAFE looks like so:

#define U16_GET_UNSAFE(s, i, c) UPRV_BLOCK_MACRO_BEGIN { \
    (c)=(s)[i]; \
    if(U16_IS_SURROGATE(c)) { \
        if(U16_IS_SURROGATE_LEAD(c)) { \
            (c)=U16_GET_SUPPLEMENTARY((c), (s)[(i)+1]); \
        } else { \
            (c)=U16_GET_SUPPLEMENTARY((s)[(i)-1], (c)); \
        } \
    } \
} UPRV_BLOCK_MACRO_END

(The BLOCK_MACRO macros are just a way to spell do...while(false) as far as I understand.)

It's true that the else block in the macro evaluates to decomposed[0-1], which is out of bounds -- but it's also in a conditional, and in a macro. That seems like this can cause quite a few false positives. Maybe this warning should be suppressed in conditionals, or macros, or some such?

(50k/70k files of chromium built with this patch, this so far is the only instance it flagged, and that's a false positive.)

[thakis]

@vabridgers: ping ^

[vabridgers]

Thanks @thakis, per @rsmith 's suggestion in the review, I'll revert this. Apologies for the inconvenience.

clang/include/clang/Sema/Sema.h

 public:
   SourceLocation getLocationOfStringLiteralByte(const StringLiteral *SL,
                                                 unsigned ByteNo) const;
 
 private:
   void CheckArrayAccess(const Expr *BaseExpr, const Expr *IndexExpr,
                         const ArraySubscriptExpr *ASE=nullptr,
                         bool AllowOnePastEnd=true, bool IndexNegated=false);
-  void CheckArrayAccess(const Expr *E);
+  void CheckArrayAccess(const Expr *E, int AllowOnePastEnd = 0);
   // Used to grab the relevant information from a FormatAttr and a
   // FunctionDeclaration.
   struct FormatStringInfo {
     unsigned FormatIdx;
     unsigned FirstDataArg;
     bool HasVAListArg;
   };
 

clang/lib/Sema/SemaChecking.cpp

if (!ND) {
     if (const MemberExpr *ME = dyn_cast<MemberExpr>(BaseExpr))
       ND = ME->getMemberDecl();
   }
 
   if (ND)
     DiagRuntimeBehavior(ND->getBeginLoc(), BaseExpr,
                         PDiag(diag::note_array_declared_here) << ND);
 }
 
-void Sema::CheckArrayAccess(const Expr *expr) {
-  int AllowOnePastEnd = 0;
-  while (expr) {
-    expr = expr->IgnoreParenImpCasts();
-    switch (expr->getStmtClass()) {
-      case Stmt::ArraySubscriptExprClass: {
-        const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(expr);
-        CheckArrayAccess(ASE->getBase(), ASE->getIdx(), ASE,
-                         AllowOnePastEnd > 0);
-        expr = ASE->getBase();
-        break;
-      }
-      case Stmt::MemberExprClass: {
-        expr = cast<MemberExpr>(expr)->getBase();
-        break;
-      }
-      case Stmt::OMPArraySectionExprClass: {
-        const OMPArraySectionExpr *ASE = cast<OMPArraySectionExpr>(expr);
-        if (ASE->getLowerBound())
-          CheckArrayAccess(ASE->getBase(), ASE->getLowerBound(),
-                           /*ASE=*/nullptr, AllowOnePastEnd > 0);
-        return;
-      }
-      case Stmt::UnaryOperatorClass: {
-        // Only unwrap the * and & unary operators
-        const UnaryOperator *UO = cast<UnaryOperator>(expr);
-        expr = UO->getSubExpr();
-        switch (UO->getOpcode()) {
-          case UO_AddrOf:
-            AllowOnePastEnd++;
-            break;
-          case UO_Deref:
-            AllowOnePastEnd--;
-            break;
-          default:
-            return;
-        }
-        break;
-      }
-      case Stmt::ConditionalOperatorClass: {
-        const ConditionalOperator *cond = cast<ConditionalOperator>(expr);
-        if (const Expr *lhs = cond->getLHS())
-          CheckArrayAccess(lhs);
-        if (const Expr *rhs = cond->getRHS())
-          CheckArrayAccess(rhs);
-        return;
-      }
-      case Stmt::CXXOperatorCallExprClass: {
-        const auto *OCE = cast<CXXOperatorCallExpr>(expr);
-        for (const auto *Arg : OCE->arguments())
-          CheckArrayAccess(Arg);
-        return;
-      }
-      default:
-        return;
-    }
-  }
-}
+void Sema::CheckArrayAccess(const Expr *expr, int AllowOnePastEnd) {
+  if (!expr)
+    return;
+
+  expr = expr->IgnoreParenCasts();
+    CheckArrayAccess(ASE->getBase(), ASE->getIdx(), ASE, AllowOnePastEnd > 0);
+    CheckArrayAccess(ASE->getBase(), AllowOnePastEnd);
+    return;
+    CheckArrayAccess(expr, /*AllowOnePastEnd=*/0);
+    return;
+    CheckArrayAccess(expr, AllowOnePastEnd);
+    return;
+      CheckArrayAccess(lhs, AllowOnePastEnd);
+      CheckArrayAccess(rhs, AllowOnePastEnd);
 
 //===--- CHECK: Objective-C retain cycles ----------------------------------//
 
 namespace {
 
 struct RetainCycleOwner {
   VarDecl *Variable = nullptr;
   SourceRange Range;

clang/test/Parser/cxx-ambig-decl-expr.cpp

 int f(unknown const x); // expected-error {{unknown type name 'unknown'}}
 
 // Disambiguating an array declarator from an array subscripting.
 void arr() {
   int x[] = {1}; // expected-note 2{{previous}}
 
   // This is array indexing not an array declarator because a comma expression
   // is not syntactically a constant-expression.
-  int(x[1,1]); // expected-warning 2{{unused}}
+  int(x[1,0]); // expected-warning 2{{unused}}
 
   // This is array indexing not an array declaration because a braced-init-list
   // is not syntactically a constant-expression.
   int(x[{0}]); // expected-error {{array subscript is not an integer}}
   struct A {
     struct Q { int n; };
     int operator[](Q);
   } a;

clang/test/SemaCXX/array-bounds.cpp

 
 // This code example tests that -Warray-bounds works with arrays that
 // are template parameters.
 template <char *sz> class Qux {
   bool test() { return sz[0] == 'a'; }
 };
 
 void f1(int a[1]) {
-  int val = a[3]; // no warning for function argumnet
+  int val = a[3]; // no warning for function argument
 }
 
 void f2(const int (&a)[2]) { // expected-note {{declared here}}
   int val = a[3];  // expected-warning {{array index 3 is past the end of the array (which contains 2 elements)}}
 }
 
 void test() {
   struct {

 
 int test_pr9296() {
     int array[2];
     return array[true]; // no-warning
 }
 
 int test_sizeof_as_condition(int flag) {
   int arr[2] = { 0, 0 }; // expected-note {{array 'arr' declared here}}
-  if (flag) 
+  if (flag)
     return sizeof(char) != sizeof(char) ? arr[2] : arr[1];
   return sizeof(char) == sizeof(char) ? arr[2] : arr[1]; // expected-warning {{array index 2 is past the end of the array (which contains 2 elements)}}
 }
 
 void test_switch() {
   switch (4) {
     case 1: {
       int arr[2];
void test_pr10771() {
 
     ((char*)foo)[sizeof(foo)] = '\0';  // expected-warning {{array index 32768 is past the end of the array (which contains 32768 elements)}}
 
     // TODO: This should probably warn, too.
     *(((char*)foo) + sizeof(foo)) = '\0';  // no-warning
 }
 
 int test_pr11007_aux(const char * restrict, ...);
-  
 // Test checking with varargs.
 void test_pr11007() {
   double a[5]; // expected-note {{array 'a' declared here}}
   test_pr11007_aux("foo", a[1000]); // expected-warning {{array index 1000 is past the end of the array}}
 }
 
 void test_rdar10916006(void)
 {

 template <> int arr<float>[1];    // expected-note {{array 'arr<float>' declared here}}
 
 void test() {
   arr<int>[1] = 0;   // ok
   arr<int>[2] = 0;   // expected-warning {{array index 2 is past the end of the array (which contains 2 elements)}}
   arr<float>[1] = 0; // expected-warning {{array index 1 is past the end of the array (which contains 1 element)}}
 }
 } // namespace var_template_array
+
+namespace PR44343 {
+  const unsigned int array[2] = {0, 1}; // expected-note 5{{array 'array' declared here}}
+
+  const int i1 = (const int)array[2]; // expected-warning {{array index 2 is past the end of the array (which contains 2 elements)}}
+  const int i2 = static_cast<const int>(array[2]); // expected-warning {{array index 2 is past the end of the array (which contains 2 elements)}}
+  const int &i3 = reinterpret_cast<const int&>(array[2]); // expected-warning {{array index 2 is past the end of the array (which contains 2 elements)}}
+  unsigned int &i4 = const_cast<unsigned int&>(array[2]); // expected-warning {{array index 2 is past the end of the array (which contains 2 elements)}}
+  int i5 = int(array[2]); // expected-warning {{array index 2 is past the end of the array (which contains 2 elements)}}
+  const unsigned int *i6 = &(1 > 0 ? array[2] : array[1]); // no warning for one-past-end element's address retrieval
+
+  // Test dynamic cast
+  struct Base {
+    virtual ~Base();
+  };
+  struct Derived : Base {
+  };
+  Base baseArr[2]; // expected-note {{array 'baseArr' declared here}}
+  Derived *d1 = dynamic_cast<Derived *>(&baseArr[2]); // FIXME: Should actually warn because dynamic_cast accesses the vptr
+  Derived &d2 = dynamic_cast<Derived &>(baseArr[2]); // expected-warning {{array index 2 is past the end of the array (which contains 2 elements)}}
+
+  // Test operator `&` in combination with operators `.` and `->`
+  struct A {
+    int n;
+  };
+  A a[2]; // expected-note {{array 'a' declared here}}
+  int *n = &a[2].n; // expected-warning {{array index 2 is past the end of the array (which contains 2 elements)}}
+  A *aPtr[2]; // expected-note {{array 'aPtr' declared here}}
+  int *n2 = &aPtr[2]->n; // expected-warning {{array index 2 is past the end of the array (which contains 2 elements)}}
+}