martong created this revision. martong added reviewers: NoQ, Szelethus, balazske, gamesh411, baloghadamsoftware, steakhal. Herald added subscribers: cfe-commits, Charusso, dkrupp, donat.nagy, mikhail.ramalho, a.sidorin, rnkovacs, szepet, xazax.hun, whisperity. Herald added a project: clang. martong added a child revision: D73898: [analyzer] StdLibraryFunctionsChecker: Add argument constraints.
Currently, ValueRange is very hard to extend with new kind of constraints. For instance, it forcibly encapsulates relations between arguments and the return value (ComparesToArgument) besides handling the regular value ranges (OutOfRange, WithinRange). ValueRange in this form is not suitable to add new constraints on arguments like "not-null". This refactor introduces a new base class ValueConstraint with an abstract apply function. Descendants must override this. There are 2 descendants: RangeConstraint and ComparisonConstraint. In the following patches I am planning to add the NotNullConstraint, and additional virtual functions like `negate()` and `warning()`. Repository: rG LLVM Github Monorepo https://reviews.llvm.org/D74973 Files: clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp
Index: clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp +++ clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp @@ -71,14 +71,6 @@ /// to us. If he doesn't, he performs additional invalidations. enum InvalidationKind { NoEvalCall, EvalCallAsPure }; - /// A pair of ValueRangeKind and IntRangeVector would describe a range - /// imposed on a particular argument or return value symbol. - /// - /// Given a range, should the argument stay inside or outside this range? - /// The special `ComparesToArgument' value indicates that we should - /// impose a constraint that involves other argument or return value symbols. - enum ValueRangeKind { OutOfRange, WithinRange, ComparesToArgument }; - // The universal integral type to use in value range descriptions. // Unsigned to make sure overflows are well-defined. typedef uint64_t RangeInt; @@ -93,44 +85,35 @@ /// ArgNo in CallExpr and CallEvent is defined as Unsigned, but /// obviously uint32_t should be enough for all practical purposes. typedef uint32_t ArgNo; - static const ArgNo Ret = std::numeric_limits<ArgNo>::max(); + static const ArgNo Ret; + + class ValueConstraint { + public: + ValueConstraint(ArgNo ArgN) : ArgN(ArgN) {} + virtual ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call, + const Summary &Summary) const = 0; + ArgNo getArgNo() const { return ArgN; } + + protected: + ArgNo ArgN; // Argument to which we apply the constraint. + }; + + /// Given a range, should the argument stay inside or outside this range? + enum RangeKind { OutOfRange, WithinRange }; /// Incapsulates a single range on a single symbol within a branch. - class ValueRange { - ArgNo ArgN; // Argument to which we apply the range. - ValueRangeKind Kind; // Kind of range definition. + class RangeConstraint : public ValueConstraint { + RangeKind Kind; // Kind of range definition. IntRangeVector Args; // Polymorphic arguments. public: - ValueRange(ArgNo ArgN, ValueRangeKind Kind, const IntRangeVector &Args) - : ArgN(ArgN), Kind(Kind), Args(Args) {} - - ArgNo getArgNo() const { return ArgN; } - ValueRangeKind getKind() const { return Kind; } - - BinaryOperator::Opcode getOpcode() const { - assert(Kind == ComparesToArgument); - assert(Args.size() == 1); - BinaryOperator::Opcode Op = - static_cast<BinaryOperator::Opcode>(Args[0].first); - assert(BinaryOperator::isComparisonOp(Op) && - "Only comparison ops are supported for ComparesToArgument"); - return Op; - } - - ArgNo getOtherArgNo() const { - assert(Kind == ComparesToArgument); - assert(Args.size() == 1); - return static_cast<ArgNo>(Args[0].second); - } + RangeConstraint(ArgNo ArgN, RangeKind Kind, const IntRangeVector &Args) + : ValueConstraint(ArgN), Kind(Kind), Args(Args) {} const IntRangeVector &getRanges() const { - assert(Kind != ComparesToArgument); return Args; } - // We avoid creating a virtual apply() method because - // it makes initializer lists harder to write. private: ProgramStateRef applyAsOutOfRange(ProgramStateRef State, const CallEvent &Call, @@ -138,30 +121,39 @@ ProgramStateRef applyAsWithinRange(ProgramStateRef State, const CallEvent &Call, const Summary &Summary) const; - ProgramStateRef applyAsComparesToArgument(ProgramStateRef State, - const CallEvent &Call, - const Summary &Summary) const; - public: ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call, - const Summary &Summary) const { + const Summary &Summary) const override { switch (Kind) { case OutOfRange: return applyAsOutOfRange(State, Call, Summary); case WithinRange: return applyAsWithinRange(State, Call, Summary); - case ComparesToArgument: - return applyAsComparesToArgument(State, Call, Summary); } - llvm_unreachable("Unknown ValueRange kind!"); + llvm_unreachable("Unknown range kind!"); } }; - /// The complete list of ranges that defines a single branch. - typedef std::vector<ValueRange> ValueRangeSet; + class ComparisonConstraint : public ValueConstraint { + BinaryOperator::Opcode Opcode; + ArgNo OtherArgN; + + public: + ComparisonConstraint(ArgNo ArgN, BinaryOperator::Opcode Opcode, + ArgNo OtherArgN) + : ValueConstraint(ArgN), Opcode(Opcode), OtherArgN(OtherArgN) {} + ArgNo getOtherArgNo() const { return OtherArgN; } + BinaryOperator::Opcode getOpcode() const { return Opcode; } + ProgramStateRef apply(ProgramStateRef State, const CallEvent &Call, + const Summary &Summary) const override; + }; + + using ValueConstraintPtr = std::shared_ptr<ValueConstraint>; + /// The complete list of constraints that defines a single branch. + typedef std::vector<ValueConstraintPtr> ConstraintSet; using ArgTypes = std::vector<QualType>; - using Ranges = std::vector<ValueRangeSet>; + using Cases = std::vector<ConstraintSet>; /// Includes information about function prototype (which is necessary to /// ensure we're modeling the right function and casting values properly), @@ -171,14 +163,14 @@ const ArgTypes ArgTys; const QualType RetTy; const InvalidationKind InvalidationKd; - Ranges Cases; - ValueRangeSet ArgConstraints; + Cases CaseConstraints; + ConstraintSet ArgConstraints; Summary(ArgTypes ArgTys, QualType RetTy, InvalidationKind InvalidationKd) : ArgTys(ArgTys), RetTy(RetTy), InvalidationKd(InvalidationKd) {} - Summary &Case(ValueRangeSet VRS) { - Cases.push_back(VRS); + Summary &Case(ConstraintSet&& CS) { + CaseConstraints.push_back(std::move(CS)); return *this; } @@ -244,9 +236,13 @@ void initFunctionSummaries(CheckerContext &C) const; }; + +const StdLibraryFunctionsChecker::ArgNo StdLibraryFunctionsChecker::Ret = + std::numeric_limits<ArgNo>::max(); + } // end of anonymous namespace -ProgramStateRef StdLibraryFunctionsChecker::ValueRange::applyAsOutOfRange( +ProgramStateRef StdLibraryFunctionsChecker::RangeConstraint::applyAsOutOfRange( ProgramStateRef State, const CallEvent &Call, const Summary &Summary) const { @@ -273,7 +269,7 @@ return State; } -ProgramStateRef StdLibraryFunctionsChecker::ValueRange::applyAsWithinRange( +ProgramStateRef StdLibraryFunctionsChecker::RangeConstraint::applyAsWithinRange( ProgramStateRef State, const CallEvent &Call, const Summary &Summary) const { @@ -330,8 +326,7 @@ return State; } -ProgramStateRef -StdLibraryFunctionsChecker::ValueRange::applyAsComparesToArgument( +ProgramStateRef StdLibraryFunctionsChecker::ComparisonConstraint::apply( ProgramStateRef State, const CallEvent &Call, const Summary &Summary) const { @@ -367,15 +362,15 @@ if (!FoundSummary) return; - // Now apply ranges. + // Now apply the constraints. const Summary &Summary = *FoundSummary; ProgramStateRef State = C.getState(); // Apply case/branch specifications. - for (const auto &VRS : Summary.Cases) { + for (const auto &VRS : Summary.CaseConstraints) { ProgramStateRef NewState = State; for (const auto &VR: VRS) { - NewState = VR.apply(NewState, Call, Summary); + NewState = VR->apply(NewState, Call, Summary); if (!NewState) break; } @@ -549,24 +544,26 @@ // Please update the list of functions in the header after editing! // - // Below are helper functions to create the summaries. - auto ArgumentCondition = [](ArgNo ArgN, ValueRangeKind Kind, - IntRangeVector Ranges) -> ValueRange { - ValueRange VR{ArgN, Kind, Ranges}; - return VR; - }; - auto ReturnValueCondition = [](ValueRangeKind Kind, - IntRangeVector Ranges) -> ValueRange { - ValueRange VR{Ret, Kind, Ranges}; - return VR; + // Below are helpers functions to create the summaries. + auto ArgumentCondition = [](ArgNo ArgN, RangeKind Kind, + IntRangeVector Ranges) { + return std::make_shared<RangeConstraint>(ArgN, Kind, Ranges); }; + struct { + auto operator()(RangeKind Kind, IntRangeVector 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 SingleValue = [](RangeInt v) { return IntRangeVector{std::pair<RangeInt, RangeInt>{v, v}}; }; - auto IsLessThan = [](ArgNo ArgN) { return IntRangeVector{{BO_LE, ArgN}}; }; + auto LessThanOrEq = BO_LE; using RetType = QualType; @@ -579,14 +576,14 @@ auto Read = [&](RetType R, RangeInt Max) { return Summary(ArgTypes{Irrelevant, Irrelevant, SizeTy}, RetType{R}, NoEvalCall) - .Case({ReturnValueCondition(ComparesToArgument, IsLessThan(2)), + .Case({ReturnValueCondition(LessThanOrEq, ArgNo(2)), ReturnValueCondition(WithinRange, Range(-1, Max))}); }; auto Fread = [&]() { return Summary(ArgTypes{Irrelevant, Irrelevant, SizeTy, Irrelevant}, RetType{SizeTy}, NoEvalCall) .Case({ - ReturnValueCondition(ComparesToArgument, IsLessThan(2)), + ReturnValueCondition(LessThanOrEq, ArgNo(2)), }); }; auto Getline = [&](RetType R, RangeInt Max) {
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits