[analyzer] StdLibraryFunctionsChecker: Add LazyRanges to support type dependent Max

[martong]

Summary

Some functions uses a platform dependent ssize_t (e.g. read). Currently, we
provide different summaries for the possible variants depending on the
canonical type of ssize_t (int, long, long long). In this patch we get rid of
this burden, thus making the administration of summaries easier. The newly
introduced LazyRangeInt is a union of a RangeInt and a function pointer. We
get the ranges lazily. By the time we need the ranges we already have a
concrete FunctionDecl set for the summary. When a function pointer is used
amongst the range values then we evaluate the function. This way we can get a
type dependent Max value and instead of providing 3 summaries to read we can
provide only one.

[xazax.hun]

I am a bit unsure what the purpose of these Max summaries are? As far as I understand the Max represents the largest value for the type of the formal parameter.

Do we really ever need to specify this in a summary? Isn't it always an error to pass a value that is larger than the formal's type can represent?

If the answer is yes, I think we should have a separate checker for catching those overflows. If the answer is no, we might want to express a simpler summary, something like cannot overflow on argument X.

What do you think?

[martong]

In D79430#2022222, @xazax.hun wrote:

I am a bit unsure what the purpose of these Max summaries are? As far as I understand the Max represents the largest value for the type of the formal parameter.

Yes, that's right. The tricky part here is that, when we write the summary we may not know what is going to be the type. In some cases (e.g. read with ssize_t) it turns out only after we looked up the FunctionDecl.

Isn't it always an error to pass a value that is larger than the formal's type can represent?
If the answer is yes, I think we should have a separate checker for catching those overflows. If the answer is no, we might want to express a simpler summary, something like cannot overflow on argument X.

The answer is yes. And yep we could have such a checker. But please read on.

Do we really ever need to specify this in a summary?

It would be possible to have a different DSL for describing the summaries. Now, the RangeConstraint requires a list of ranges, but that's just some technical detail. So, instead of

.ArgConstraint(ArgumentCondition(0, WithinRange, Range(0, Max)))

we could have

.ArgConstraint(ArgumentCondition(0, WithinRange, GreaterThanOrEqTo(0)))

. In this case, however, GreaterThanOrEqTo would return a range(0, Max). And Max still would be something that we can evaluate only lazily (once we have the FunctionDecl).
I prefer the explicit Range(0, Max) notion, because then the range is seen immediately.

[martong]

Since D80016 we are able to look up types in the TU, so we can get the maximum value from the found type.

clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

class StdLibraryFunctionsChecker
 
   protected:
     ArgNo ArgN; // Argument to which we apply the constraint.
 
     /// Do polymorphic sanity check on the constraint.
     virtual bool sanityCheck(const FunctionDecl *FD) const { return true; }
   };
 
+  using RangeFun = RangeInt(const FunctionDecl *, ArgNo, BasicValueFactory &);
+  using RangeFunPtr = RangeFun *;
+  class LazyRangeInt {
+    union {
+      RangeInt Int;
+      RangeFunPtr Fun;
+    } Storage;
+    enum { K_Int, K_Fun } Kind;
+
+  public:
+    LazyRangeInt(int Int) : Kind(K_Int) { Storage.Int = Int; }
+    LazyRangeInt(RangeFunPtr Fun) : Kind(K_Fun) { Storage.Fun = Fun; }
+    RangeInt eval(const FunctionDecl *FD, ArgNo ArgN,
+                  BasicValueFactory &BVF) const {
+      if (Kind == K_Int)
+        return Storage.Int;
+      return Storage.Fun(FD, ArgN, BVF);
+    }
+  };
+
+  static RangeInt Max(const FunctionDecl *FD, ArgNo ArgN,
+                      BasicValueFactory &BVF) {
+    return BVF.getMaxValue(getArgType(FD, ArgN)).getLimitedValue();
+  }
+
+  using LazyIntRangeVector = std::vector<std::pair<LazyRangeInt, LazyRangeInt>>;
+
   /// Given a range, should the argument stay inside or outside this range?
   enum RangeKind { OutOfRange, WithinRange };
 
   /// Encapsulates a single range on a single symbol within a branch.
   class RangeConstraint : public ValueConstraint {
     RangeKind Kind;      // Kind of range definition.
-    IntRangeVector Args; // Polymorphic arguments.
+    mutable IntRangeVector Ranges;
+    LazyIntRangeVector LazyRanges;
 
   public:
-    RangeConstraint(ArgNo ArgN, RangeKind Kind, const IntRangeVector &Args)
-        : ValueConstraint(ArgN), Kind(Kind), Args(Args) {}
+    RangeConstraint(ArgNo ArgN, RangeKind Kind, const IntRangeVector &Ranges)
+        : ValueConstraint(ArgN), Kind(Kind), Ranges(Ranges) {}
 
-    const IntRangeVector &getRanges() const {
-      return Args;
+    RangeConstraint(ArgNo ArgN, RangeKind Kind,
+                    const LazyIntRangeVector &Ranges)
+        : ValueConstraint(ArgN), Kind(Kind), LazyRanges(Ranges) {}
+
+    const IntRangeVector &getRanges(const FunctionDecl *FD,
+                                    BasicValueFactory &BVF) const {
+      if (Ranges.size())
+        return Ranges;
+      for (const std::pair<LazyRangeInt, LazyRangeInt> &LazyR : LazyRanges) {
+        Ranges.push_back({LazyR.first.eval(FD, ArgN, BVF),
+                          LazyR.second.eval(FD, ArgN, BVF)});
+      }
+      return Ranges;
     }
 
   private:
     ProgramStateRef applyAsOutOfRange(ProgramStateRef State,
                                       const CallEvent &Call,
                                       const Summary &Summary) const;
     ProgramStateRef applyAsWithinRange(ProgramStateRef State,
                                        const CallEvent &Call,
Summary &Case(ConstraintSet&& CS) {
       return *this;
     }
     Summary &ArgConstraint(ValueConstraintPtr VC) {
       ArgConstraints.push_back(VC);
       return *this;
     }
 
     void setFunctionDecl(const FunctionDecl *FD) { this->FD = FD; }
+    const FunctionDecl *getFunctionDecl() const { return 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);
     }
ProgramStateRef StdLibraryFunctionsChecker::RangeConstraint::applyAsOutOfRange(
   ProgramStateManager &Mgr = State->getStateManager();
   SValBuilder &SVB = Mgr.getSValBuilder();
   BasicValueFactory &BVF = SVB.getBasicValueFactory();
   ConstraintManager &CM = Mgr.getConstraintManager();
   QualType T = Summary.getArgType(getArgNo());
   SVal V = getArgSVal(Call, getArgNo());
 
   if (auto N = V.getAs<NonLoc>()) {
-    const IntRangeVector &R = getRanges();
+    const IntRangeVector &R = getRanges(Summary.getFunctionDecl(), BVF);
     size_t E = R.size();
     for (size_t I = 0; I != E; ++I) {
       const llvm::APSInt &Min = BVF.getValue(R[I].first, T);
       const llvm::APSInt &Max = BVF.getValue(R[I].second, T);
       assert(Min <= Max);
       State = CM.assumeInclusiveRange(State, *N, Min, Max, false);
       if (!State)
         break;
ProgramStateRef StdLibraryFunctionsChecker::RangeConstraint::applyAsWithinRange(
   // and then cut away all holes in R one by one.
   //
   // E.g. consider a range list R as [A, B] and [C, D]
   // -------+--------+------------------+------------+----------->
   //        A        B                  C            D
   // Then we assume that the value is not in [-inf, A - 1],
   // then not in [D + 1, +inf], then not in [B + 1, C - 1]
   if (auto N = V.getAs<NonLoc>()) {
-    const IntRangeVector &R = getRanges();
+    const IntRangeVector &R = getRanges(Summary.getFunctionDecl(), BVF);
     size_t E = R.size();
 
     const llvm::APSInt &MinusInf = BVF.getMinValue(T);
     const llvm::APSInt &PlusInf = BVF.getMaxValue(T);
 
     const llvm::APSInt &Left = BVF.getValue(R[0].first - 1ULL, T);
     if (Left != PlusInf) {
       assert(MinusInf <= Left);
void StdLibraryFunctionsChecker::initFunctionSummaries(
   // 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
-  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
 
   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
   // value of the argument should be min(UCharMax, IntMax). This just happen
   // to be true for commonly used and well tested instruction set
   // architectures, but not for others.
   const RangeInt UCharRangeMax =
void StdLibraryFunctionsChecker::initFunctionSummaries(
   // than this argument. If we made a promotion, and the size argument
   // is equal to, say, 10, then we'd impose a range of [0, 10] on the
   // return value, however the correct range is [-1, 10].
   //
   // Please update the list of functions in the header after editing!
 
   // Below are helpers functions to create the summaries.
   auto ArgumentCondition = [](ArgNo ArgN, RangeKind Kind,
-                              IntRangeVector Ranges) {
+                              LazyIntRangeVector Ranges) {
     return std::make_shared<RangeConstraint>(ArgN, Kind, Ranges);
   };
   struct {
-    auto operator()(RangeKind Kind, IntRangeVector Ranges) {
+    auto operator()(RangeKind Kind, LazyIntRangeVector Ranges) {
       return std::make_shared<RangeConstraint>(Ret, Kind, Ranges);
     }
     auto operator()(BinaryOperator::Opcode Op, ArgNo OtherArgN) {
       return std::make_shared<ComparisonConstraint>(Ret, Op, OtherArgN);
     }
   } ReturnValueCondition;
-  auto Range = [](RangeInt b, RangeInt e) {
-    return IntRangeVector{std::pair<RangeInt, RangeInt>{b, e}};
+  auto Range = [](LazyRangeInt b, LazyRangeInt e) {
+    return LazyIntRangeVector{std::pair<LazyRangeInt, LazyRangeInt>{b, e}};
   };
-  auto SingleValue = [](RangeInt v) {
-    return IntRangeVector{std::pair<RangeInt, RangeInt>{v, v}};
+  auto SingleValue = [](LazyRangeInt v) {
+    return LazyIntRangeVector{std::pair<LazyRangeInt, LazyRangeInt>{v, v}};
   };
   auto LessThanOrEq = BO_LE;
   auto NotNull = [&](ArgNo ArgN) {
     return std::make_shared<NotNullConstraint>(ArgN);
   };
 
   using RetType = QualType;
-  // Templates for summaries that are reused by many functions.
-  auto Getc = [&]() {
-    return Summary(ArgTypes{Irrelevant}, 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)
-        .Case({
-            ReturnValueCondition(LessThanOrEq, ArgNo(2)),
-        })
-        .ArgConstraint(NotNull(ArgNo(0)));
-  };
-  auto Fwrite = [&]() {
-    return Summary(
-               ArgTypes{ConstVoidPtrRestrictTy, Irrelevant, SizeTy, Irrelevant},
-               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)
-        .Case({ReturnValueCondition(WithinRange, {{-1, -1}, {1, Max}})});
-  };
 
   // The isascii() family of functions.
   // The behavior is undefined if the value of the argument is not
   // representable as unsigned char or is not equal to EOF. See e.g. C99
   // 7.4.1.2 The isalpha function (p: 181-182).
   addToFunctionSummaryMap(
       "isalnum",
       Summary(ArgTypes{IntTy}, RetType{IntTy}, EvalCallAsPure)
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.
-  addToFunctionSummaryMap("getc", Getc());
-  addToFunctionSummaryMap("fgetc", Getc());
+  addToFunctionSummaryMap(
+      {"getc", "fgetc"},
+      Summary(ArgTypes{Irrelevant}, RetType{IntTy}, NoEvalCall)
+          .Case({ReturnValueCondition(WithinRange,
+                                      {{EOFv, EOFv}, {0, UCharRangeMax}})}));
   addToFunctionSummaryMap(
       "getchar", Summary(ArgTypes{}, RetType{IntTy}, NoEvalCall)
                      .Case({ReturnValueCondition(
                          WithinRange, {{EOFv, EOFv}, {0, UCharRangeMax}})}));
 
   // read()-like functions that never return more than buffer size.
-  // We are not sure how ssize_t is defined on every platform, so we
-  // provide three variants that should cover common cases.
-  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());
+  addToFunctionSummaryMap(
+      {"read", "write"},
+      Summary(NoEvalCall)
+          .Case({ReturnValueCondition(LessThanOrEq, ArgNo(2)),
+                 ReturnValueCondition(WithinRange, Range(-1, Max))}));
+  addToFunctionSummaryMap({"fread", "fwrite"},
+                          Summary(NoEvalCall)
+                              .Case({
+                                  ReturnValueCondition(LessThanOrEq, ArgNo(2)),
+                              })
+                              .ArgConstraint(NotNull(ArgNo(0))));
+
   // getline()-like functions either fail or read at least the delimiter.
-  addToFunctionSummaryMap("getline",
-                          {Getline(IntTy, IntMax), Getline(LongTy, LongMax),
-                           Getline(LongLongTy, LongLongMax)});
-  addToFunctionSummaryMap("getdelim",
-                          {Getline(IntTy, IntMax), Getline(LongTy, LongMax),
-                           Getline(LongLongTy, LongLongMax)});
+  addToFunctionSummaryMap(
+      {"getline", "getdelim"},
+      Summary(NoEvalCall)
+          .Case({ReturnValueCondition(WithinRange, {{-1, -1}, {1, Max}})}));
 
   // Functions for testing.
   if (ChecksEnabled[CK_StdCLibraryFunctionsTesterChecker]) {
     addToFunctionSummaryMap(
         "__two_constrained_args",
         Summary(ArgTypes{IntTy, IntTy}, RetType{IntTy}, EvalCallAsPure)
             .ArgConstraint(ArgumentCondition(0U, WithinRange, SingleValue(1)))
             .ArgConstraint(ArgumentCondition(1U, WithinRange, SingleValue(1))));
     addToFunctionSummaryMap(
         "__arg_constrained_twice",
         Summary(ArgTypes{IntTy}, RetType{IntTy}, EvalCallAsPure)
             .ArgConstraint(ArgumentCondition(0U, OutOfRange, SingleValue(1)))
             .ArgConstraint(ArgumentCondition(0U, OutOfRange, SingleValue(2))));
     addToFunctionSummaryMap(
         "__defaultparam",
         Summary(ArgTypes{Irrelevant, IntTy}, RetType{IntTy}, EvalCallAsPure)
             .ArgConstraint(NotNull(ArgNo(0))));
     addToFunctionSummaryMap("__variadic",
                             Summary(ArgTypes{VoidPtrTy, ConstCharPtrTy},
                                     RetType{IntTy}, EvalCallAsPure)
                                 .ArgConstraint(NotNull(ArgNo(0)))
                                 .ArgConstraint(NotNull(ArgNo(1))));
+    addToFunctionSummaryMap(
+        "__lazy_range",
+        Summary(ArgTypes{IntTy, IntTy}, RetType{IntTy}, EvalCallAsPure)
+            .ArgConstraint(ArgumentCondition(0, WithinRange, Range(0, 100)))
+            .ArgConstraint(ArgumentCondition(1, WithinRange, Range(0, Max))));
   }
 }
 
 void ento::registerStdCLibraryFunctionsChecker(CheckerManager &mgr) {
   mgr.registerChecker<StdLibraryFunctionsChecker>();
 }
 
 bool ento::shouldRegisterStdCLibraryFunctionsChecker(const CheckerManager &mgr) {

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

 
 int __variadic(void *stream, const char *format, ...);
 void test_arg_constraint_on_variadic_fun() {
   __variadic(0, "%d%d", 1, 2); // \
   // report-warning{{Function argument constraint is not satisfied}} \
   // bugpath-warning{{Function argument constraint is not satisfied}} \
   // bugpath-note{{Function argument constraint is not satisfied}}
 }
+
+int __lazy_range(int, int);
+void test_lazy_range(int a, int b) {
+  __lazy_range(a, b);
+  clang_analyzer_eval(a >= 0 && a <= 100 && b >= 0 && b <= __INT_MAX__); // \
+  // report-warning{{TRUE}} \
+  // bugpath-warning{{TRUE}} \
+  // bugpath-note{{TRUE}} \
+  // bugpath-note{{'a' is >= 0}} \
+  // bugpath-note{{'a' is <= 100}} \
+  // bugpath-note{{'b' is >= 0}} \
+  // bugpath-note{{'b' is <= __INT_MAX__}} \
+  // bugpath-note{{Left side of '&&' is true}} \
+  // bugpath-note{{Left side of '&&' is true}} \
+  // bugpath-note{{Left side of '&&' is true}}
+}