[analyzer] Fix assertion failure with conflicting prototype calls

[steakhal]

Summary

It turns out we can reach the Init.castAs<nonlock::CompoundVal>()
expression with other kinds of SVals. Such as by nonloc::ConcreteInt
in this example: https://godbolt.org/z/s4fdxrcs9

int buffer[10];
void b();
void top() {
  b(&buffer);
}
void b(int *c) {
  *c = 42; // would crash
}

In this example, we try to store 42 to the Elem{buffer, 0}.

This situation can appear if the CallExpr refers to a function
declaration without prototype. In such cases, the engine will pick the
redecl of the referred function decl which has function body, hence has
a function prototype.

This weird situation will have an interesting effect to the AST, such as
the argument at the callsite will miss a cast, which would cast the
int (*)[10] expression into int *, which means that when we evaluate
the *c = 42 expression, we want to bind 42 to an array, causing the
crash.

Look at the AST of the callsite with and without the function prototype: https://godbolt.org/z/Gncebcbdb
The only difference is that without the proper function prototype, we will not have the ImplicitCastExpr BitCasting from int (*)[10] to int * to match the expected type of the parameter declaration.

In this patch, I'm proposing to emit a cast in the mentioned edge-case,
to bind the argument value of the expected type to the parameter.

I'm only proposing this if the runtime definition has exactly the same
number of parameters as the callsite feeds it by arguments.
If that's not the case, I believe, we are better off by binding Unknown
to those parameters.

[martong]

Hmm, seems like the conflicting prototype (i.e. the obsolescent use of zero parameters) is needed to reproduce the assertion failure. That makes me wonder, how does the redecl chain of b looks like? Is void b() chained with void b(int*), or are they represented independently from each other? I guess they form the same redecl chain. Which drives us to the next questions.
When the analyzer reaches the CallExpr b(&buffer) which FunctionDecl does it see? Is it b() or b(int*)? My bet, it sees and works with b(). Could we detect if the arguments of the CallExpr does not match the parameters of the FunctionDecl? And if that is the case, could we iterate through the redecl chain to find an appropriate matching FunctionDecl? That would be b(int*) in this case ... and the original bindArray() should work then.

[martong]

A similar situation could happen if we reinterpret cast pointers, etc. so the situation is not limited to conflicting function prototypes.

Please provide tests for those cases.

[steakhal]

In D136162#3865081, @martong wrote:

Hmm, seems like the conflicting prototype (i.e. the obsolescent use of zero parameters) is needed to reproduce the assertion failure. That makes me wonder, how does the redecl chain of b looks like? Is void b() chained with void b(int*), or are they represented independently from each other? I guess they form the same redecl chain. Which drives us to the next questions.
When the analyzer reaches the CallExpr b(&buffer) which FunctionDecl does it see? Is it b() or b(int*)? My bet, it sees and works with b().

Yes, they form the same redecl chain, indeed.
The call b(&buffer) refers to the void () decl - with no parameters.
The range of ->redecls() of that decl has two items:
The decl of void (), and the decl of void (int *).

Could we detect if the arguments of the CallExpr does not match the parameters of the FunctionDecl? And if that is the case, could we iterate through the redecl chain to find an appropriate matching FunctionDecl? That would be b(int*) in this case ... and the original bindArray() should work then.

Good idea. Actually, the CFG already refers to the void () delc, so we should probably change it there instead of doing the same in the CSA.
Let me investigate this route.

In D136162#3865094, @martong wrote:

A similar situation could happen if we reinterpret cast pointers, etc. so the situation is not limited to conflicting function prototypes.

Please provide tests for those cases.

It was a harsh guess on my part, simply by looking at the missing ElementRegion, I thought that I could reconstruct the example by some reinterpret-cast tricks - but I could not pull it off.
Disregard that part.

[NoQ]

In this example, we try to store 42 to the Elem{buffer, 0}.

In this case the natural question is, why does it go through bindArray()? We're not binding an array. Can we try to preserve the contract that bindArray() only deals with arrays?

@martong's comment makes sense to me, it sounds like this could be a case of CallEvent::getRuntimeDefinition() not picking up the right definition, at least not consistently.

[steakhal]

• Updated the summary.
• Implementing a completely new approach focusing on the runtime definition & argument-parameter binding

[steakhal]

In D136162#3869645, @NoQ wrote:

In this example, we try to store 42 to the Elem{buffer, 0}.

In this case the natural question is, why does it go through bindArray()? We're not binding an array. Can we try to preserve the contract that bindArray() only deals with arrays?

@martong's comment makes sense to me, it sounds like this could be a case of CallEvent::getRuntimeDefinition() not picking up the right definition, at least not consistently.

Thank you @martong and @NoQ for the helpful comments. They really helped a lot to look at this problem from a new perspective!
I hope, this new approach is more aligned with your expectations.

[tomasz-kaminski-sonarsource]

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

490

Previously we didng make bindings if ArgVal was unknown, and we may want to preserve this invariant.

clang/test/Analysis/region-store.c

66

I would like to see an example where the called function is implicitly defined.

[tomasz-kaminski-sonarsource]

clang/test/Analysis/region-store.c

66

After rethinking it, I have not idea how to construct that example.

[steakhal]

clang/test/Analysis/region-store.c

66

I could not construct such an example.
It seems like clang errors out for cases when an implicit declaration of a call mismatches with the definition of that function.
https://godbolt.org/z/rM9ajeTf7

[NoQ]

Ok so you're saying that it's not just a wrong Decl but there's like an entire cast-expression missing in the AST? This fix is probably good enough for us but it begs a question, what does CodeGen do in such cases? Does it also need to emit a cast instruction into LLVM IR that doesn't correspond to anything in the AST? Or is this entirely about our weird pointer cast handling, that needs to act even when the numeric value of the pointer doesn't change?

[NoQ]

clang/test/Analysis/region-store.c

66

Yeah, if you scroll really far to the right, you'll see that the first error is actually a warning auto-promoted to an error. So you can pass -Wno-implicit-function-declaration and it'll disappear. Not sure what to do with the other error though, it really does notice that the implicit definition conflicts with the later explicit definition. So, dunno.

[steakhal]

In D136162#3873392, @NoQ wrote:

Ok so you're saying that it's not just a wrong Decl but there's like an entire cast-expression missing in the AST? This fix is probably good enough for us but it begs a question, what does CodeGen do in such cases? Does it also need to emit a cast instruction into LLVM IR that doesn't correspond to anything in the AST? Or is this entirely about our weird pointer cast handling, that needs to act even when the numeric value of the pointer doesn't change?

Good question. The IR is identical for the two cases - except for metadata markers e.g. for deb info, etc.
So, it might be simply that the "C" language just doesn't care if there is a bitcast or not in the AST, because the hardware register is just an untyped register; hence this ImplicitCastExpr (bitcast) is getting lowered as a noop at the IR level.

Unfortunately, it's beyond my expertise. Do you think we should invite someone, like Shafik or Aaron?

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

490

IDK what are the implications of not having a binding or having a binding to unknown.
I'll change this anyway. Thanks for noticing.

clang/test/Analysis/region-store.c

66

Yup, I should have been more clear on this. See the test, I'm also passing the -Wno-implicit-function-declaration :)
Maybe Shafik or Aaron knows some weird stuff about how to make it 'compile'. WDYT?

[martong]

Thanks for the update. Nice Work!

clang/test/Analysis/region-store.c

66

Interestingly, GCC trunk compiles it without errors, the warnings are there though.

[steakhal]

In D136162#3874953, @martong wrote:

Thanks for the update. Nice Work!

Thanks! I'll land this tomorrow.

clang/test/Analysis/region-store.c

66

Hm, interesting.

[steakhal]

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

490

Hm, I tried to move the unknown check after the cast. It would result in a difference in the last example:

void c(); // expected-warning {{a function declaration without a prototype is deprecated in all versions of C and is treated as a zero-parameter prototype in C2x, conflicting with a subsequent definition}}
void missingPrototypeCallsiteMismatchingArgsAndParams() {
  // expected-warning@+1 {{passing arguments to 'c' without a prototype is deprecated in all versions of C and is not supported in C2x}}
  c(&buffer, &buffer);
}
void c(int *c) { // expected-note {{conflicting prototype is here}}
  clang_analyzer_dump(c); // ???
  *c = 42; // no-crash
}

The clang_analyzer_dump(c) would result in &SymRegion{reg_$0<int * c>} instead of Unknown.
Which is not exactly what I want. I want to bind Unknown in case the cast would result in Unknown or some weird parameter passing is detected, what we don't want to support/model, such as mismatching number of arguments & parameters, etc.

clang/lib/StaticAnalyzer/Core/CallEvent.cpp

if (isTransparentUnion(ParamType) &&
 
     // Wrap it with compound value.
     return SVB.makeCompoundVal(ParamType, CompoundSVals);
   }
 
   return Value;
 }
 
+/// Cast the argument value to the type of the parameter at the function
+/// declaration.
+/// Returns the argument value if it didn't need a cast.
+/// Or returns the cast argument if it needed a cast.
+/// Or returns 'Unknown' if it would need a cast but the callsite and the
+/// runtime definition don't match in terms of argument and parameter count.
+static SVal castArgToParamTypeIfNeeded(const CallEvent &Call, unsigned ArgIdx,
+                                       SVal ArgVal, SValBuilder &SVB) {
+  const FunctionDecl *RTDecl =
+      Call.getRuntimeDefinition().getDecl()->getAsFunction();
+  const auto *CallExprDecl = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
+
+  if (!RTDecl || !CallExprDecl)
+    return ArgVal;
+
+  // The function decl of the Call (in the AST) will not have any parameter
+  // declarations, if it was 'only' declared without a prototype. However, the
+  // engine will find the appropriate runtime definition - basically a
+  // redeclaration, which has a function body (and a function prototype).
+  if (CallExprDecl->hasPrototype() || !RTDecl->hasPrototype())
+    return ArgVal;
+
+  // Only do this cast if the number arguments at the callsite matches with
+  // the parameters at the runtime definition.
+  if (Call.getNumArgs() != RTDecl->getNumParams())
+    return UnknownVal();
+
+  const Expr *ArgExpr = Call.getArgExpr(ArgIdx);
+  const ParmVarDecl *Param = RTDecl->getParamDecl(ArgIdx);
+  return SVB.evalCast(ArgVal, Param->getType(), ArgExpr->getType());
+}
+
 static void addParameterValuesToBindings(const StackFrameContext *CalleeCtx,
                                          CallEvent::BindingsTy &Bindings,
                                          SValBuilder &SVB,
                                          const CallEvent &Call,
                                          ArrayRef<ParmVarDecl*> parameters) {
   MemRegionManager &MRMgr = SVB.getRegionManager();
 
   // If the function has fewer parameters than the call has arguments, we simply
if (Call.getKind() != CE_CXXAllocator)
       if (Call.isArgumentConstructedDirectly(Call.getASTArgumentIndex(Idx)))
         continue;
 
     // TODO: Allocators should receive the correct size and possibly alignment,
     // determined in compile-time but not represented as arg-expressions,
     // which makes getArgSVal() fail and return UnknownVal.
     SVal ArgVal = Call.getArgSVal(Idx);
     const Expr *ArgExpr = Call.getArgExpr(Idx);
-    if (!ArgVal.isUnknown()) {
-      Loc ParamLoc = SVB.makeLoc(
-          MRMgr.getParamVarRegion(Call.getOriginExpr(), Idx, CalleeCtx));
-      Bindings.push_back(
-          std::make_pair(ParamLoc, processArgument(ArgVal, ArgExpr, *I, SVB)));
-    }
-  }
+
+    if (ArgVal.isUnknown())
+      continue;
+
+    // Cast the argument value to match the type of the parameter in some
+    // edge-cases.
+    ArgVal = castArgToParamTypeIfNeeded(Call, Idx, ArgVal, SVB);
+
 
   // FIXME: Variadic arguments are not handled at all right now.
 }
 
 const ConstructionContext *CallEvent::getConstructionContext() const {
   const StackFrameContext *StackFrame = getCalleeStackFrame(0);
   if (!StackFrame)
     return nullptr;

clang/test/Analysis/region-store.c

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,unix,debug.ExprInspection -verify -analyzer-config eagerly-assume=false %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,unix,debug.ExprInspection \
+// RUN:    -verify -analyzer-config eagerly-assume=false -std=c99 %s \
+// RUN:    -Wno-implicit-function-declaration
 
 int printf(const char *restrict,...);
 
+void clang_analyzer_eval(int);
+void clang_analyzer_dump(int*);
+
 // Testing core functionality of the region store.
 // radar://10127782
 int compoundLiteralTest(void) {
     int index = 0;
     for (index = 0; index < 2; index++) {
         int thing = (int []){0, 1}[index];
         printf("thing: %i\n", thing);
     }

 };
 int initStruct(struct X *st);
 int structOffsetBindingIsInvalidated(int length, int i){
   struct X l;
   initStruct(&l);
   return l.mem; // no-warning
 }
 
-void clang_analyzer_eval(int);
 void testConstraintOnRegionOffset(int *values, int length, int i){
   if (values[1] == 4) {
     values[i] = 5;
     clang_analyzer_eval(values[1] == 4);// expected-warning {{UNKNOWN}}
   }
 }
 
 int initArray(int *values);
 void testConstraintOnRegionOffsetStack(int *values, int length, int i) {
   if (values[0] == 4) {
     initArray(values);
     clang_analyzer_eval(values[0] == 4);// expected-warning {{UNKNOWN}}
   }
 }
+
+int buffer[10];
+void b(); // expected-warning {{a function declaration without a prototype is deprecated in all versions of C and is treated as a zero-parameter prototype in C2x, conflicting with a subsequent definition}}
+void missingPrototypeCallsiteMatchingArgsAndParams() {
+  // expected-warning@+1 {{passing arguments to 'b' without a prototype is deprecated in all versions of C and is not supported in C2x}}
+  b(&buffer);
+}
+void b(int *c) { // expected-note {{conflicting prototype is here}}
+  clang_analyzer_dump(c); // expected-warning {{&Element{buffer,0 S64b,int}}}
+  *c = 42; // no-crash
+}
+
+void c(); // expected-warning {{a function declaration without a prototype is deprecated in all versions of C and is treated as a zero-parameter prototype in C2x, conflicting with a subsequent definition}}
+void missingPrototypeCallsiteMismatchingArgsAndParams() {
+  // expected-warning@+1 {{passing arguments to 'c' without a prototype is deprecated in all versions of C and is not supported in C2x}}
+  c(&buffer, &buffer);
+}
+void c(int *c) { // expected-note {{conflicting prototype is here}}
+  clang_analyzer_dump(c); // expected-warning {{Unknown}}
+  *c = 42; // no-crash
+}