[analyzer][NFC] StdLibraryFunctionsChecker: Add empty Signatures

[martong]

Summary

In the C language, functions must not be overloaded. In this patch I am adding
empty Signatures. During adding a summary for a function with a given name,
if we provide an empty Signature then we assume that all visible function
declarations in the given TU share the same signature (i.e. their
FunctionProtoType is the same). This makes the administration of adding
summaries for the standard C library (and other C libraries) way easier.

[balazske]

The empty signature is used to make add of C API functions easy because only the function name must be specified, not all types of parameters?

[balazske]

An empty signature means really that the whole signature is "irrelevant"? It is like all types and number of arguments is irrelevant. Probably that would be a better name, instead of empty use isIrrelevant.

[xazax.hun]

I am a bit unsure about this change. C libraries might be consumed in C++ projects and C++ projects might be free to overload those functions. Does the effort needed to specify the signatures justify not supporting that (probably unintentional) name collisions in C++?

[martong]

In D79423#2022167, @balazske wrote:

An empty signature means really that the whole signature is "irrelevant"? It is like all types and number of arguments is irrelevant. Probably that would be a better name, instead of empty use isIrrelevant.

Yes, that's right. I like what you propose for the naming, thanks!

[martong]

In D79423#2022251, @xazax.hun wrote:

I am a bit unsure about this change. C libraries might be consumed in C++ projects and C++ projects might be free to overload those functions.

I don't think that could be a concern.
Actually, redefinition of a reserved name either in the C or in the C++ standard library is undefined behavior:

C++11:
[reserved.names]

1. The C ++ standard library reserves the following kinds of names:

— macros
— global names
— names with external linkage
...
Each name from the Standard C library declared with external linkage is reserved to the implementation
for use as a name with extern "C" linkage, both in namespace std and in the global namespace.

2. If a program declares or defines a name in a context where it is reserved, other than as explicitly allowed by this Clause, its behavior is undefined.

C99 (7.1) has something similar. And from glibc manual:
The names of all library types, macros, variables and functions that come from the ISO C standard are reserved unconditionally; your program may not redefine these names. All other library names are reserved if your program explicitly includes the header file that defines or declares them.

On the other hand, we may be able to discover the mentioned UB, and it may be worth to emit a bug-report in such cases.

Does the effort needed to specify the signatures justify not supporting that (probably unintentional) name collisions in C++?

No, we still support adding summaries to overloaded C++ functions. But then the user must specify the signature (possibly with Irrelevant types) that matches only one FunctionDecl. Hope this answers your question.

[martong]

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

263

TODO rename to isIrrelevant.

[xazax.hun]

In D79423#2022812, @martong wrote:

I don't think that could be a concern.
Actually, redefinition of a reserved name either in the C or in the C++ standard library is undefined behavior:

I disagree. As you mentioned in another revision, we plan to model functions beyond the C and C++ standard library. We cannot prevent name collisions for those other libraries (and sometimes we cannot even prevent unintended name collisions with the standard libraries).
I think to reduce the risk of applying the wrong summary to a function worth the effort of spelling the signature out (since it only needs to be done once).

[balazske]

Probably something like IsCStdLibraryFunction can be included in the signature, and empty signature is allowed only for functions that are in a C standard library.

[martong]

• Rename 'empty' -> 'irrelevant'

[martong]

In D79423#2022920, @xazax.hun wrote:

In D79423#2022812, @martong wrote:

I don't think that could be a concern.
Actually, redefinition of a reserved name either in the C or in the C++ standard library is undefined behavior:

I disagree. As you mentioned in another revision, we plan to model functions beyond the C and C++ standard library. We cannot prevent name collisions for those other libraries (and sometimes we cannot even prevent unintended name collisions with the standard libraries).
I think to reduce the risk of applying the wrong summary to a function worth the effort of spelling the signature out (since it only needs to be done once).

I see your point Gabor. I agree that it would be the best if we could give a precise signatures to every summary. But we can't.
There are two difficulties to provide proper signatures:

1. Some function types contain non-builtin types. E.g. FILE*. We cannot get this type as easily as we do with builtin types (we can get builtins simply from the ASTContext). In case of such a compound type, we should be digging up the type from the AST, and that can be done by doing a lookup. But instead of looking up the type of one parameter, it is better to do the lookup for the function itself. So, in these cases we rather use the Irrelevant type in the Signature. Signatures with irrelevant types are not precise, they may match accidentally other functions.
2. Cppcheck config files does not provide any signature, so it would require overly too much manual work to synthesize the signatures (that may not be precise anyway, see the above point).

However, not having a signature is not a problem in the case of LibC and POSIX. This is because LibC implementations do provide POSIX compatiblity, so they define the functions from POSIX (e.g. e.g. glibc). Besides they claim

All other library names are reserved if your program explicitly includes the header file that defines or declares them.

In my understanding this includes the names defined by POSIX.
Consequently, user code should not redefine - or add any overload in case of C++- to any functions defined in the standard C, C++ or POSIX library. This is also related to C++.

So, here is my suggestion.

• LibC, STL and POSIX: We should allow empty/irrelevant signatures for standardized functions. If the user code provides any colliding function then we emit an error.
• Other libraries: We should be more rigorous with these functions and we could require a signature for each function. If the user code provides any colliding function then we just emit a warning and the corresponding summary is not added and will not be used. One example is when the user enables summaries from OpenSSL where we have a summary for let's say void encrypt(FILE*), and the Signature is void(Irrelevant). If the user code defines encrypt(double) that seems to be okay as it overloads with encrypt(FILE*) but our signature matching mechanism cannot cope with this, so we rather back out and keep the conservative evaluation for the function.

TLDR; having empty signatures makes it possible to easily add summaries for standard functions that we know they must have only one definition and they cannot be overloaded.

[martong]

In D79423#2023150, @balazske wrote:

Probably something like IsCStdLibraryFunction can be included in the signature, and empty signature is allowed only for functions that are in a C standard library.

Yeah, we could do something like that, but also with POSIX. Furthermore, I think we shall extend to that direction once we want to support libs other than libC, STL and POSIX.

[xazax.hun]

In D79423#2025001, @martong wrote:

1. Some function types contain non-builtin types. E.g. FILE*. We cannot get this type as easily as we do with builtin types (we can get builtins simply from the ASTContext). In case of such a compound type, we should be digging up the type from the AST, and that can be done by doing a lookup.

I see the problem, but as far as I understand, this is not unique to libC or Posix. Any libraries that use non-primitive types (which is most of them) will suffer from the very same problem. So I anticipated that this type lookup from the ASTContext needs to be implemented regardless of the irrelevant signature functionality.

[martong]

We had a separate discussion with @xazax.hun. Let me summarize the outcome. We agreed that we should try our best to provide signatures for all functions (this affects child patches, particularly the POSIX related D79433). Probably, we are not going to need this patch anymore, once we will have done that work.

[martong]

Since D80016 we are able to look up types in the TU, so this patch is no longer needed. We'd like to be as precise with the function signatures as possible.

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

class StdLibraryFunctionsChecker
   bool static isIrrelevant(QualType T) { return T.isNull(); }
 
   // The signature of a function we want to describe with a summary. This is a
   // concessive signature, meaning there may be irrelevant types in the
   // signature which we do not check against a function with concrete types.
   struct Signature {
     const ArgTypes ArgTys;
     const QualType RetTy;
+    Signature(){};
     Signature(ArgTypes ArgTys, QualType RetTy) : ArgTys(ArgTys), RetTy(RetTy) {
       assertRetTypeSuitableForSignature(RetTy);
       for (size_t I = 0, E = ArgTys.size(); I != E; ++I) {
         QualType ArgTy = ArgTys[I];
         assertArgTypeSuitableForSignature(ArgTy);
       }
     }
     bool matches(const FunctionDecl *FD) const;
+    bool isIrrelevant() const {
+      return StdLibraryFunctionsChecker::isIrrelevant(RetTy) &&
+             ArgTys.size() == 0;
+    }
 
   private:
     static void assertArgTypeSuitableForSignature(QualType T) {
       assert((T.isNull() || !T->isVoidType()) &&
              "We should have no void types in the spec");
       assert((T.isNull() || T.isCanonical()) &&
              "We should only have canonical types in the spec");
     }
class Summary {
     // The function to which the summary applies. This is set after lookup and
     // match to the signature.
     const FunctionDecl *FD = nullptr;
 
   public:
     Summary(ArgTypes ArgTys, QualType RetTy, InvalidationKind InvalidationKd)
         : Sign(ArgTys, RetTy), InvalidationKd(InvalidationKd) {}
 
+    // Create with irrelevant signature.
+    Summary(InvalidationKind InvalidationKd) : InvalidationKd(InvalidationKd) {}
+
     Summary &Case(ConstraintSet&& CS) {
       CaseConstraints.push_back(std::move(CS));
       return *this;
     }
     Summary &ArgConstraint(ValueConstraintPtr VC) {
       ArgConstraints.push_back(VC);
       return *this;
     }
 
     void setFunctionDecl(const FunctionDecl *FD) { this->FD = FD; }
 
     InvalidationKind getInvalidationKd() const { return InvalidationKd; }
     const Cases &getCaseConstraints() const { return CaseConstraints; }
     const ConstraintSet &getArgConstraints() const { return ArgConstraints; }
 
     QualType getArgType(ArgNo ArgN) const {
       return StdLibraryFunctionsChecker::getArgType(FD, ArgN);
     }
 
     bool matchesSignature(const FunctionDecl *FD) const {
       return Sign.matches(FD) && validate(FD);
     }
+    bool hasIrrelevantSignature() const { return Sign.isIrrelevant(); }
 
   private:
     // Once we know the exact type of the function then do sanity check on all
     // the given constraints.
     bool validate(const FunctionDecl *FD) const {
       for (const auto &Case : CaseConstraints)
         for (const ValueConstraintPtr &Constraint : Case)
           if (!Constraint->validate(FD))
case NoEvalCall:
     // evaluated by another checker, or evaluated conservatively.
     return false;
   }
   llvm_unreachable("Unknown invalidation kind!");
 }
 
 bool StdLibraryFunctionsChecker::Signature::matches(
     const FunctionDecl *FD) const {
+  // Irrelevant signature matches everything.
+  if (isIrrelevant())
+    return true;
+
   // Check number of arguments:
   if (FD->param_size() != ArgTys.size())
     return false;
 
   // Check return type.
-  if (!isIrrelevant(RetTy))
+  if (!StdLibraryFunctionsChecker::isIrrelevant(RetTy))
     if (RetTy != FD->getReturnType().getCanonicalType())
       return false;
 
   // Check argument types.
   for (size_t I = 0, E = ArgTys.size(); I != E; ++I) {
     QualType ArgTy = ArgTys[I];
-    if (isIrrelevant(ArgTy))
+    if (StdLibraryFunctionsChecker::isIrrelevant(ArgTy))
       continue;
     if (ArgTy != FD->getParamDecl(I)->getType().getCanonicalType())
       return false;
   }
 
   return true;
 }
 
struct AddToFunctionSummaryMap {
     // Add a summary to a FunctionDecl found by lookup. The lookup is performed
     // by the given Name, and in the global scope. The summary will be attached
     // to the found FunctionDecl only if the signatures match.
     void operator()(StringRef Name, Summary S) {
       IdentifierInfo &II = ACtx.Idents.get(Name);
       auto LookupRes = ACtx.getTranslationUnitDecl()->lookup(&II);
       if (LookupRes.size() == 0)
         return;
-      for (Decl *D : LookupRes) {
-        if (auto *FD = dyn_cast<FunctionDecl>(D)) {
-          if (S.matchesSignature(FD)) {
-            S.setFunctionDecl(FD);
-            auto Res = Map.insert({FD->getCanonicalDecl(), S});
-            assert(Res.second && "Function already has a summary set!");
-            (void)Res;
-            return;
-          }
-        }
-      }
-    }
+      // Get all FunctionDecls.
+      SmallVector<FunctionDecl *, 2> FDs;
+      for (Decl *D : LookupRes)
+        if (auto *FD = dyn_cast<FunctionDecl>(D))
+          FDs.push_back(FD);
+      // Irrelevant signatures should be used only without name overloading.
+      if (FDs.size() > 1 && S.hasIrrelevantSignature())
+        return;
+      for (FunctionDecl *FD : FDs) {
     // Add several summaries for the given name.
     void operator()(StringRef Name, const std::vector<Summary> &Summaries) {
       for (const Summary &S : Summaries)
         operator()(Name, S);
     }
   } addToFunctionSummaryMap(ACtx, FunctionSummaryMap);
 
   // We are finally ready to define specifications for all supported functions.