[analyzer] StdLibraryFunctionsChecker: Add support to lookup types

[martong]

Summary

In this patch I am trying to get rid of the Irrelevant types from the
signatures of the functions from the standard C library. For that I've
introduced lookupType() to be able to lookup arbitrary types in the global
scope. This makes it possible to define the signatures precisely.

Note 1) fread's signature is now fixed to have the proper FILE *restrict
type when C99 is the language.
Note 2) There are still existing Irrelevant types, but they are all from
POSIX. I am planning to address those together with the missing POSIX functions
(in D79433).

[balazske]

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

905

The Optional<QualType> can be left out from the right side expressions (in the ? operator part). (A QualType should be assignable to Optional<QualType>.)

[martong]

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

905

No that cannot be left out. Implicit conversion does not play when trying to determine the common type for the 2nd and 3rd argument of the ternary op. https://stackoverflow.com/questions/32251419/c-ternary-operator-conditional-operator-and-its-implicit-type-conversion-r
So, removing the explicit type I get a compile error.

[balazske]

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

905

Still I do not like that code. Probably this is better then:

Optional<QualType> FilePtrTy, FilePtrRestrictTy;
if (FileTy) {
  FilePtrTy = ACtx.getPointerType(*FileTy);
  FilePtrRestrictTy = ACtx.getLangOpts().C99
                          ? ACtx.getRestrictType(*FilePtrTy) // FILE *restrict
                          : *FilePtrTy)
}

[martong]

• Rebase to master

[martong]

• Add if (FileTy)

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

905

Ok, I added the if.

[balazske]

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

897

There is a ASTContext::getFILEType that can be used for this. (But if more types are needed the lookupType must be used again.)

[martong]

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

897

Yeah, didn't realize that we have getFILEType until now. It's unfortunate that I added the tests for FILE in this sense.

getFILEType can return a null QualType, which unfortunately can be mixed with Irrelevant. I'd like to avoid that. Still, we could initialize the Optional<QualType> with the help of getFILEType. Maybe in a later patch it would be worth to do that (and then refactor the lookup.c[pp] tests too).

On the other hand, since we are going to use lookupType extensively with other types, I don't see much benefit to make an exemption to FILE.

[xazax.hun]

A high level comment.

Trying to match function signatures is not a unique problem! In fact, almost all of the checks the analyzer have is trying to solve the very some problem.
One of the methods we have at this point is called CallDescription, see here: https://github.com/llvm/llvm-project/blob/master/clang/lib/StaticAnalyzer/Core/CallEvent.cpp#L358

Moreover, I would assume something similar needs to be done for APINotes.

Do you think it would be possible to extend the CallDescription interface to match your needs? In that case all of the checks could profit from this work.
What do you think?

[martong]

In D80016#2063234, @xazax.hun wrote:

A high level comment.

Trying to match function signatures is not a unique problem! In fact, almost all of the checks the analyzer have is trying to solve the very some problem.
One of the methods we have at this point is called CallDescription, see here: https://github.com/llvm/llvm-project/blob/master/clang/lib/StaticAnalyzer/Core/CallEvent.cpp#L358

Moreover, I would assume something similar needs to be done for APINotes.

Do you think it would be possible to extend the CallDescription interface to match your needs? In that case all of the checks could profit from this work.
What do you think?

Yes, viewing from this angle, I am trying to solve a problem here that perhaps could be handled by CallDescription and CallDescriptionMap with some extensions.

Here are the differences between the two approaches so far:

• CallDescription is evaluated for every call event (e.g. checkPreCall), the names - strings - are compared; containing declaration contexts are compared by names (see CallEvent::isCalled). Contrary to this, summaries are associated directly to FunctionDecls, so during a call event we compare two FunctionDecl pointers.
• A CallDescription does not support overloading on different types if the number of parameters are the same. With summaries this works.
• A CallDescriptionMap is a static map with fixed number of entries. Contrary to this, the FunctionSummaryMap contains an entry (a summary) for a function only if we can lookup a matching FunctionDecl in the TU. The initialization of the FunctionSummaryMap happens lazily during the first call event.

Except the lack of proper overloading support, these differences are in the implementation. So, yes, giving it more thought, maybe we could refactor CallDescriptionMap to behave this way, but that would be some very heavy refactoring :) Still, would be possible, I guess.

Moreover, I would assume something similar needs to be done for APINotes.

Yes, I agree, I could not find out (yet) how the do it, but somehow they must match a given FunctionDecl to the Name in the YAML.

---

I was thinking about an alternative method for a long time now.
Making one step backwards: what we need is to be able to associate some data to a given function. And we can perfectly identify the function with it's prototype written in C/C++.
So, what if we'd be able to write a CallDescriptionMap (or a FunctionSummaryMap) like this:

CallDescriptionMap<FnCheck> Callbacks = {
    {{"void *memcpy(void *dest, const void *src, size_t n)"}, &CStringChecker::evalMemcpy},
    ...

Actually, we could reuse the Parser and the Sema itself to solve this issue. In fact, we could achieve this by reusing the ExternalASTSource together with the ASTImporter to find precisely the existing redecl chain in the TU for memcpy.

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

 StdLibraryFunctionsChecker::findFunctionSummary(const CallEvent &Call,
                                                 CheckerContext &C) const {
   const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
   if (!FD)
     return None;
   return findFunctionSummary(FD, C);
 }
 
+llvm::Optional<QualType> lookupType(StringRef Name, const ASTContext &ACtx) {
+  IdentifierInfo &II = ACtx.Idents.get(Name);
+  auto LookupRes = ACtx.getTranslationUnitDecl()->lookup(&II);
+  if (LookupRes.size() == 0)
+    return None;
+
+  // Prioritze typedef declarations.
+  // This is needed in case of C struct typedefs. E.g.:
+  //   typedef struct FILE FILE;
+  // In this case, we have a RecordDecl 'struct FILE' with the name 'FILE' and
+  // we have a TypedefDecl with the name 'FILE'.
+  for (Decl *D : LookupRes) {
+    if (auto *TD = dyn_cast<TypedefNameDecl>(D))
+      return ACtx.getTypeDeclType(TD).getCanonicalType();
+  }
+  assert(LookupRes.size() == 1 && "Type identifier should be unique");
+  auto *D = cast<TypeDecl>(LookupRes.front());
+  return ACtx.getTypeDeclType(D).getCanonicalType();
+}
+
 void StdLibraryFunctionsChecker::initFunctionSummaries(
     CheckerContext &C) const {
   if (!FunctionSummaryMap.empty())
     return;
 
   SValBuilder &SVB = C.getSValBuilder();
   BasicValueFactory &BVF = SVB.getBasicValueFactory();
   const ASTContext &ACtx = BVF.getContext();
 
   // These types are useful for writing specifications quickly,
   // New specifications should probably introduce more types.
   // Some types are hard to obtain from the AST, eg. "ssize_t".
   // In such cases it should be possible to provide multiple variants
   // of function summary for common cases (eg. ssize_t could be int or long
   // or long long, so three summary variants would be enough).
   // Of course, function variants are also useful for C++ overloads.
   const QualType IntTy = ACtx.IntTy;
   const QualType LongTy = ACtx.LongTy;
   const QualType LongLongTy = ACtx.LongLongTy;
   const QualType SizeTy = ACtx.getSizeType();
   const QualType VoidPtrTy = ACtx.VoidPtrTy; // void *
   const QualType VoidPtrRestrictTy =
-      ACtx.getRestrictType(VoidPtrTy); // void *restrict
+      ACtx.getLangOpts().C99 ? ACtx.getRestrictType(VoidPtrTy) // void *restrict
+                             : VoidPtrTy;
   const QualType ConstVoidPtrTy =
       ACtx.getPointerType(ACtx.VoidTy.withConst()); // const void *
   const QualType ConstCharPtrTy =
       ACtx.getPointerType(ACtx.CharTy.withConst()); // const char *
   const QualType ConstVoidPtrRestrictTy =
-      ACtx.getRestrictType(ConstVoidPtrTy); // const void *restrict
+      ACtx.getLangOpts().C99
+          ? ACtx.getRestrictType(ConstVoidPtrTy) // const void *restrict
+          : ConstVoidPtrTy;
 
   const RangeInt IntMax = BVF.getMaxValue(IntTy).getLimitedValue();
   const RangeInt LongMax = BVF.getMaxValue(LongTy).getLimitedValue();
   const RangeInt LongLongMax = BVF.getMaxValue(LongLongTy).getLimitedValue();
 
   // Set UCharRangeMax to min of int or uchar maximum value.
   // The C standard states that the arguments of functions like isalpha must
   // be representable as an unsigned char. Their type is 'int', so the max
void StdLibraryFunctionsChecker::initFunctionSummaries(
   auto SingleValue = [](RangeInt v) {
     return IntRangeVector{std::pair<RangeInt, RangeInt>{v, v}};
   };
   auto LessThanOrEq = BO_LE;
   auto NotNull = [&](ArgNo ArgN) {
     return std::make_shared<NotNullConstraint>(ArgN);
   };
 
+  Optional<QualType> FileTy = lookupType("FILE", ACtx);
+  Optional<QualType> FilePtrTy, FilePtrRestrictTy;
+  if (FileTy) {
+    // FILE *
+    FilePtrTy = ACtx.getPointerType(*FileTy);
+    // FILE *restrict
+    FilePtrRestrictTy =
+        ACtx.getLangOpts().C99 ? ACtx.getRestrictType(*FilePtrTy) : *FilePtrTy;
+  }
+
   using RetType = QualType;
   // Templates for summaries that are reused by many functions.
   auto Getc = [&]() {
-    return Summary(ArgTypes{Irrelevant}, RetType{IntTy}, NoEvalCall)
+    return Summary(ArgTypes{*FilePtrTy}, RetType{IntTy}, NoEvalCall)
         .Case({ReturnValueCondition(WithinRange,
                                     {{EOFv, EOFv}, {0, UCharRangeMax}})});
   };
   auto Read = [&](RetType R, RangeInt Max) {
     return Summary(ArgTypes{Irrelevant, Irrelevant, SizeTy}, RetType{R},
                    NoEvalCall)
         .Case({ReturnValueCondition(LessThanOrEq, ArgNo(2)),
                ReturnValueCondition(WithinRange, Range(-1, Max))});
   };
   auto Fread = [&]() {
-    return Summary(ArgTypes{VoidPtrRestrictTy, Irrelevant, SizeTy, Irrelevant},
-                   RetType{SizeTy}, NoEvalCall)
+    return Summary(
+               ArgTypes{VoidPtrRestrictTy, SizeTy, SizeTy, *FilePtrRestrictTy},
         .Case({
             ReturnValueCondition(LessThanOrEq, ArgNo(2)),
         })
         .ArgConstraint(NotNull(ArgNo(0)));
   };
   auto Fwrite = [&]() {
-    return Summary(
-               ArgTypes{ConstVoidPtrRestrictTy, Irrelevant, SizeTy, Irrelevant},
+    return Summary(ArgTypes{ConstVoidPtrRestrictTy, SizeTy, SizeTy,
+                            *FilePtrRestrictTy},
                    RetType{SizeTy}, NoEvalCall)
         .Case({
             ReturnValueCondition(LessThanOrEq, ArgNo(2)),
         })
         .ArgConstraint(NotNull(ArgNo(0)));
   };
   auto Getline = [&](RetType R, RangeInt Max) {
     return Summary(ArgTypes{Irrelevant, Irrelevant, Irrelevant}, RetType{R},
                    NoEvalCall)
addToFunctionSummaryMap(
           .Case({ArgumentCondition(0U, WithinRange,
                                    {{'0', '9'}, {'A', 'F'}, {'a', 'f'}}),
                  ReturnValueCondition(OutOfRange, SingleValue(0))})
           .Case({ArgumentCondition(0U, OutOfRange,
                                    {{'0', '9'}, {'A', 'F'}, {'a', 'f'}}),
                  ReturnValueCondition(WithinRange, SingleValue(0))}));
 
   // The getc() family of functions that returns either a char or an EOF.
+  if (FilePtrTy) {
     addToFunctionSummaryMap("getc", Getc());
     addToFunctionSummaryMap("fgetc", Getc());
+  }
   addToFunctionSummaryMap(
       "getchar", Summary(ArgTypes{}, RetType{IntTy}, NoEvalCall)
                      .Case({ReturnValueCondition(
                          WithinRange, {{EOFv, EOFv}, {0, UCharRangeMax}})}));
 
   // read()-like functions that never return more than buffer size.
+  if (FilePtrRestrictTy) {
+    addToFunctionSummaryMap("fread", Fread());
+    addToFunctionSummaryMap("fwrite", Fwrite());
+  }
+
   // We are not sure how ssize_t is defined on every platform, so we
   // provide three variants that should cover common cases.
+  // FIXME these are actually defined by POSIX and not by the C standard, we
+  // should handle them together with the rest of the POSIX functions.
   addToFunctionSummaryMap("read", {Read(IntTy, IntMax), Read(LongTy, LongMax),
                                    Read(LongLongTy, LongLongMax)});
   addToFunctionSummaryMap("write", {Read(IntTy, IntMax), Read(LongTy, LongMax),
                                     Read(LongLongTy, LongLongMax)});
-  addToFunctionSummaryMap("fread", Fread());
-  addToFunctionSummaryMap("fwrite", Fwrite());
+
   // getline()-like functions either fail or read at least the delimiter.
+  // FIXME these are actually defined by POSIX and not by the C standard, we
+  // should handle them together with the rest of the POSIX functions.
   addToFunctionSummaryMap("getline",
                           {Getline(IntTy, IntMax), Getline(LongTy, LongMax),
                            Getline(LongLongTy, LongLongMax)});
   addToFunctionSummaryMap("getdelim",
                           {Getline(IntTy, IntMax), Getline(LongTy, LongMax),
                            Getline(LongLongTy, LongLongMax)});
 
   // Functions for testing.

clang/test/Analysis/std-c-library-functions-arg-constraints.c

if (x > 255) { // \
     // bugpath-note{{Function argument constraint is not satisfied}}
 
     (void)ret;
   }
 }
 
 typedef struct FILE FILE;
 typedef typeof(sizeof(int)) size_t;
-size_t fread(void *restrict, size_t, size_t, FILE *);
+size_t fread(void *restrict, size_t, size_t, FILE *restrict);
 void test_notnull_concrete(FILE *fp) {
   fread(0, sizeof(int), 10, fp); // \
   // report-warning{{Function argument constraint is not satisfied}} \
   // bugpath-warning{{Function argument constraint is not satisfied}} \
   // bugpath-note{{Function argument constraint is not satisfied}}
 }
 void test_notnull_symbolic(FILE *fp, int *buf) {
   fread(buf, sizeof(int), 10, fp);

clang/test/Analysis/std-c-library-functions-lookup.c

+// RUN: %clang_analyze_cc1 %s \
+// RUN:   -analyzer-checker=core \
+// RUN:   -analyzer-checker=apiModeling.StdCLibraryFunctions \
+// RUN:   -analyzer-config apiModeling.StdCLibraryFunctions:DisplayLoadedSummaries=true \
+// RUN:   -analyzer-checker=debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -triple i686-unknown-linux 2>&1 | FileCheck %s
+
+// CHECK: Loaded summary for: unsigned int fread(void *restrict, size_t, size_t, FILE *restrict)
+
+typedef typeof(sizeof(int)) size_t;
+typedef struct FILE FILE;
+size_t fread(void *restrict, size_t, size_t, FILE *restrict);
+
+// Must have at least one call expression to initialize the summary map.
+int bar(void);
+void foo() {
+  bar();
+}

clang/test/Analysis/std-c-library-functions-lookup.cpp

+// RUN: %clang_analyze_cc1 %s \
+// RUN:   -analyzer-checker=core \
+// RUN:   -analyzer-checker=apiModeling.StdCLibraryFunctions \
+// RUN:   -analyzer-config apiModeling.StdCLibraryFunctions:DisplayLoadedSummaries=true \
+// RUN:   -analyzer-checker=debug.ExprInspection \
+// RUN:   -analyzer-config eagerly-assume=false \
+// RUN:   -triple i686-unknown-linux 2>&1 | FileCheck %s
+
+//      CHECK: Loaded summary for: size_t fread(void *, size_t, size_t, FILE *)
+//  CHECK-NOT: Loaded summary for: size_t fread(void *, size_t, size_t, MyFile *)
+
+typedef unsigned int size_t;
+typedef struct FILE FILE;
+size_t fread(void *, size_t, size_t, FILE *);
+
+struct MyFile;
+size_t fread(void *, size_t, size_t, MyFile *);
+
+// Must have at least one call expression to initialize the summary map.
+int bar(void);
+void foo() {
+  bar();
+}

clang/test/Analysis/std-c-library-functions.c

 // CHECK-NEXT: Loaded summary for: int isprint(int)
 // CHECK-NEXT: Loaded summary for: int ispunct(int)
 // CHECK-NEXT: Loaded summary for: int isspace(int)
 // CHECK-NEXT: Loaded summary for: int isupper(int)
 // CHECK-NEXT: Loaded summary for: int isxdigit(int)
 // CHECK-NEXT: Loaded summary for: int getc(FILE *)
 // CHECK-NEXT: Loaded summary for: int fgetc(FILE *)
 // CHECK-NEXT: Loaded summary for: int getchar()
+// CHECK-NEXT: Loaded summary for: unsigned int fread(void *restrict, size_t, size_t, FILE *restrict)
+// CHECK-NEXT: Loaded summary for: unsigned int fwrite(const void *restrict, size_t, size_t, FILE *restrict)
 // CHECK-NEXT: Loaded summary for: ssize_t read(int, void *, size_t)
 // CHECK-NEXT: Loaded summary for: ssize_t write(int, const void *, size_t)
-// CHECK-NEXT: Loaded summary for: unsigned int fread(void *restrict, size_t, size_t, FILE *)
-// CHECK-NEXT: Loaded summary for: unsigned int fwrite(const void *restrict, size_t, size_t, FILE *restrict)
 // CHECK-NEXT: Loaded summary for: ssize_t getline(char **, size_t *, FILE *)
 
 void clang_analyzer_eval(int);
 
 int glob;
 
 typedef struct FILE FILE;
 #define EOF -1
if (y >= 0) {
       // -1 overflows on promotion!
       clang_analyzer_eval(y <= sizeof(glob)); // expected-warning{{FALSE}}
     }
   } else {
     clang_analyzer_eval(x == -1); // expected-warning{{TRUE}}
   }
 }
 
-size_t fread(void *restrict, size_t, size_t, FILE *);
+size_t fread(void *restrict, size_t, size_t, FILE *restrict);
 size_t fwrite(const void *restrict, size_t, size_t, FILE *restrict);
 void test_fread_fwrite(FILE *fp, int *buf) {
 
   size_t x = fwrite(buf, sizeof(int), 10, fp);
   clang_analyzer_eval(x <= 10); // expected-warning{{TRUE}}
 
   size_t y = fread(buf, sizeof(int), 10, fp);
   clang_analyzer_eval(y <= 10); // expected-warning{{TRUE}}