diff --git a/clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp b/clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp --- a/clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp @@ -53,21 +53,17 @@ class RegionRawOffsetV2 { private: const SubRegion *baseRegion; - SVal byteOffset; - - RegionRawOffsetV2() - : baseRegion(nullptr), byteOffset(UnknownVal()) {} + NonLoc byteOffset; public: RegionRawOffsetV2(const SubRegion *base, NonLoc offset) : baseRegion(base), byteOffset(offset) { assert(base); } - NonLoc getByteOffset() const { return byteOffset.castAs(); } + NonLoc getByteOffset() const { return byteOffset; } const SubRegion *getRegion() const { return baseRegion; } - static RegionRawOffsetV2 computeOffset(ProgramStateRef state, - SValBuilder &svalBuilder, - SVal location); + static std::optional + computeOffset(ProgramStateRef State, SValBuilder &SVB, SVal Location); void dump() const; void dumpToStream(raw_ostream &os) const; @@ -169,16 +165,16 @@ ProgramStateRef state = checkerContext.getState(); SValBuilder &svalBuilder = checkerContext.getSValBuilder(); - const RegionRawOffsetV2 &rawOffset = - RegionRawOffsetV2::computeOffset(state, svalBuilder, location); + const std::optional &RawOffset = + RegionRawOffsetV2::computeOffset(state, svalBuilder, location); - if (!rawOffset.getRegion()) + if (!RawOffset) return; - NonLoc ByteOffset = rawOffset.getByteOffset(); + NonLoc ByteOffset = RawOffset->getByteOffset(); // CHECK LOWER BOUND - const MemSpaceRegion *SR = rawOffset.getRegion()->getMemorySpace(); + const MemSpaceRegion *SR = RawOffset->getRegion()->getMemorySpace(); if (!llvm::isa(SR)) { // A pointer to UnknownSpaceRegion may point to the middle of // an allocated region. @@ -199,7 +195,7 @@ // CHECK UPPER BOUND DefinedOrUnknownSVal Size = - getDynamicExtent(state, rawOffset.getRegion(), svalBuilder); + getDynamicExtent(state, RawOffset->getRegion(), svalBuilder); if (auto KnownSize = Size.getAs()) { auto [state_withinUpperBound, state_exceedsUpperBound] = compareValueToThreshold(state, ByteOffset, *KnownSize, svalBuilder); @@ -307,84 +303,55 @@ } #endif -// Lazily computes a value to be used by 'computeOffset'. If 'val' -// is unknown or undefined, we lazily substitute '0'. Otherwise, -// return 'val'. -static inline SVal getValue(SVal val, SValBuilder &svalBuilder) { - return val.isUndef() ? svalBuilder.makeZeroArrayIndex() : val; -} - -// Scale a base value by a scaling factor, and return the scaled -// value as an SVal. Used by 'computeOffset'. -static inline SVal scaleValue(ProgramStateRef state, - NonLoc baseVal, CharUnits scaling, - SValBuilder &sb) { - return sb.evalBinOpNN(state, BO_Mul, baseVal, - sb.makeArrayIndex(scaling.getQuantity()), - sb.getArrayIndexType()); -} - -// Add an SVal to another, treating unknown and undefined values as -// summing to UnknownVal. Used by 'computeOffset'. -static SVal addValue(ProgramStateRef state, SVal x, SVal y, - SValBuilder &svalBuilder) { - // We treat UnknownVals and UndefinedVals the same here because we - // only care about computing offsets. - if (x.isUnknownOrUndef() || y.isUnknownOrUndef()) - return UnknownVal(); - - return svalBuilder.evalBinOpNN(state, BO_Add, x.castAs(), - y.castAs(), - svalBuilder.getArrayIndexType()); -} - -/// Compute a raw byte offset from a base region. Used for array bounds -/// checking. -RegionRawOffsetV2 RegionRawOffsetV2::computeOffset(ProgramStateRef state, - SValBuilder &svalBuilder, - SVal location) -{ - const MemRegion *region = location.getAsRegion(); - SVal offset = UndefinedVal(); - - while (region) { - switch (region->getKind()) { - default: { - if (const SubRegion *subReg = dyn_cast(region)) { - if (auto Offset = getValue(offset, svalBuilder).getAs()) - return RegionRawOffsetV2(subReg, *Offset); - } - return RegionRawOffsetV2(); - } - case MemRegion::ElementRegionKind: { - const ElementRegion *elemReg = cast(region); - SVal index = elemReg->getIndex(); - if (!isa(index)) - return RegionRawOffsetV2(); - QualType elemType = elemReg->getElementType(); +/// For a given Location that can be represented as a symbolic expression +/// Arr[Idx] (or perhaps Arr[Idx1][Idx2] etc.), return the parent memory block +/// Arr and the distance of Location from the beginning of Arr (expressed in a +/// NonLoc that specifies the number of CharUnits). Returns nullopt when these +/// cannot be determined. +std::optional +RegionRawOffsetV2::computeOffset(ProgramStateRef State, SValBuilder &SVB, + SVal Location) { + QualType T = SVB.getArrayIndexType(); + auto Calc = [&SVB, State, T](BinaryOperatorKind Op, NonLoc LHS, NonLoc RHS) { + // We will use this utility to add and multiply values. + return SVB.evalBinOpNN(State, Op, LHS, RHS, T).getAs(); + }; + + const MemRegion *Region = Location.getAsRegion(); + NonLoc Offset = SVB.makeZeroArrayIndex(); + + while (Region) { + if (const auto *ERegion = dyn_cast(Region)) { + if (const auto Index = ERegion->getIndex().getAs()) { + QualType ElemType = ERegion->getElementType(); // If the element is an incomplete type, go no further. - ASTContext &astContext = svalBuilder.getContext(); - if (elemType->isIncompleteType()) - return RegionRawOffsetV2(); - - // Update the offset. - offset = addValue(state, - getValue(offset, svalBuilder), - scaleValue(state, - index.castAs(), - astContext.getTypeSizeInChars(elemType), - svalBuilder), - svalBuilder); - - if (offset.isUnknownOrUndef()) - return RegionRawOffsetV2(); - - region = elemReg->getSuperRegion(); - continue; + if (ElemType->isIncompleteType()) + return std::nullopt; + + // Perform Offset += Index * sizeof(ElemType); then continue the offset + // calculations with SuperRegion: + NonLoc Size = SVB.makeArrayIndex( + SVB.getContext().getTypeSizeInChars(ElemType).getQuantity()); + if (auto Delta = Calc(BO_Mul, *Index, Size)) { + if (auto NewOffset = Calc(BO_Add, Offset, *Delta)) { + Offset = *NewOffset; + Region = ERegion->getSuperRegion(); + continue; + } + } } + } else if (const auto *SRegion = dyn_cast(Region)) { + // NOTE: The dyn_cast<>() is expected to succeed, it'd be very surprising + // to see a MemSpaceRegion at this point. + // FIXME: We may return with {, 0} even if we didn't handle any + // ElementRegion layers. I think that this behavior was introduced + // accidentally by 8a4c760c204546aba566e302f299f7ed2e00e287 in 2011, so + // it may be useful to review it in the future. + return RegionRawOffsetV2(SRegion, Offset); } + return std::nullopt; } - return RegionRawOffsetV2(); + return std::nullopt; } void ento::registerArrayBoundCheckerV2(CheckerManager &mgr) {