[analyzer][NFC] Use std::optional instead of custom "empty" state

[donat.nagy]

Summary

This commit eliminates the uninitialized error state from the class RegionRawOffsetV2 (which is locally used by the Clang Static Analyzer checker alpha.security.ArrayBoundV2) and replaces its use with std::optional.

Motivated by https://reviews.llvm.org/D148355#inline-1437928

Moreover, the code of RegionRawOffsetV2::computeOffset() is rearranged to clarify its behavior. The helper function getValue() was eliminated by picking a better initial value for the variable Offset; two other helper functions were replaced by the lambda function Calc() because this way it doesn't need to take the "context" objects as parameters.

This reorganization revealed some surprising (but not outright buggy) behavior that's marked by a FIXME and will be revisited in a separate commit.

[steakhal]

Approved, assuming we prefer std::nullopt over the default construction of std::optional and you clang-format the affected hunks, such as the declaration of computeOffset.
Make sure the commit message complies with:

• https://www.llvm.org/docs/Phabricator.html#committing-a-change
• https://llvm.org/docs/DeveloperPolicy.html#commit-messages

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

305–306

I'd recommend using the more explicit version for such cases.

[donat.nagy]

As I was finalizing this commit, I noticed that the logic of RegionRawOffsetV2::computeOffset() is presented in a crazy unconventional way; so I rewrote it (while preserving the original behavior).

The most convoluted part was that the old code initialized the offset variable to UnknownVal(), then compensated for this choice by introducing a function getValue that always substituted zero when it encountered this UnknownVal() (no other effect placed UnknownVal() into that variable without immediately returning afterwards). I suspect that this initial value was introduced to avoid the analysis of load expressions that do not involve any array indexing (i.e. don't have ElementRegion layers), but that logic was broken by a commit in 2011.

@steakhal Can you provide another review for this extended version of the patch?

[steakhal]

Sure, Ill look at this on Tuesday.

[donat.nagy]

Thanks!

[donat.nagy]

@steakhal Could you review this change when you have some time for it?

I'm planning to stabilize and de-alpha this checker with a series of incremental changes; and it'd be good have this commit and the unrelated tweak https://reviews.llvm.org/D149460 merged before I start working on the next steps. My plans for the near future:

• Replace the prototype-level error reporting with real, detailed, useful messages. Implementing this may require some code reorganization to preserve and pass around the details information.
• Perform an early return when there is no real indexing (there are no ElementRegion layers in the load operation).
• Reconsider the handling of multidimensional arrays: the current code (in fact the function computeOffset that I'm refactoring there) says that arr[0][10] is a valid way to index int arr[4][5] which not what the users would expect (in this simple case, even clang-tidy knows that "array index 10 is past the end of the array", but ArrayBoundsV2 implements complex logic to compare the index with the whole memory region allocated for the array). I'm leaning towards switching to "normal" behavior here.
• Report situations like struct foo {int field;} arr[5]; arr[10].field = 123; -- the current implementation doesn't "see" these because this is writing a FieldRegion (which happens to be inside an ElementRegion, but the checker doesn't look for that that).

I'm also open to feedback/suggestions connected to these plans. It's likely that the code added by the current NFC commit will be rewritten by the followup changes, but I think it's still useful to merge it, because it documents the switch from the old implementation.

[steakhal]

In D149259#4315393, @donat.nagy wrote:

@steakhal Could you review this change when you have some time for it?

I didn't forget about this one. It's in progress, but it's difficult to squeeze this in. The ETA is probably tomorrow.

I'm planning to stabilize and de-alpha this checker with a series of incremental changes; and it'd be good have this commit and the unrelated tweak https://reviews.llvm.org/D149460 merged before I start working on the next steps.

Good luck with moving this out. It's gonna be bumpy.

My plans for the near future:

• Replace the prototype-level error reporting with real, detailed, useful messages. Implementing this may require some code reorganization to preserve and pass around the details information.

IMO this is the most important step, yes.

• Perform an early return when there is no real indexing (there are no ElementRegion layers in the load operation).
• Reconsider the handling of multidimensional arrays: the current code (in fact the function computeOffset that I'm refactoring there) says that arr[0][10] is a valid way to index int arr[4][5] which not what the users would expect (in this simple case, even clang-tidy knows that "array index 10 is past the end of the array", but ArrayBoundsV2 implements complex logic to compare the index with the whole memory region allocated for the array). I'm leaning towards switching to "normal" behavior here.

In fact, I believe it's UB to index an int arr[4][5] multi-dimensional array like arr[0][10].

• Report situations like struct foo {int field;} arr[5]; arr[10].field = 123; -- the current implementation doesn't "see" these because this is writing a FieldRegion (which happens to be inside an ElementRegion, but the checker doesn't look for that that).

+1

I'm also open to feedback/suggestions connected to these plans. It's likely that the code added by the current NFC commit will be rewritten by the followup changes, but I think it's still useful to merge it, because it documents the switch from the old implementation.

I'm looking forward to these change. Count me for the reviews.
Also, note that this is in production here, so it will take me time to verify the patches. So, I'd probably prefer to have a patch stack, and do the evaluation for some selected patches - basically bundling the stack into a few (1-2) checkpoints.
It would mean that the reviews would be done for each revision, but the verification (prior to landing anything) would be done at the selected stages.
WDYT?

[donat.nagy]

It's gonna be bumpy.

Yup :) but it's not impossible...

Also, note that this is in production here, so it will take me time to verify the patches. So, I'd probably prefer to have a patch stack, and do the evaluation for some selected patches - basically bundling the stack into a few (1-2) checkpoints.
It would mean that the reviews would be done for each revision, but the verification (prior to landing anything) would be done at the selected stages.
WDYT?

It would be effective to adopt a workflow where the individual commits are quickly reviewed for design directions and visible code quality issues (to avoid dead ends and keep the rebasing on a manageable level); but the complete verification and the upstreaming is done later, in bundles (to avoid wasting time on repeated verifications). Feel free to give "Seems fine for now; start working on the next commit; this will be verified and merged later." reviews after handling the bulk of obvious issues. (The "Seems fine for now" declarations don't need to be completely final, I'll fix code quality issues even if you only spot them during the final verification.)

[steakhal]

We only had a single new issue after this patch. This is well within what I would be comfortable with. I'll investigate the case anyway. It's likely something flaky.
Feel free to land this in the meantime.

[steakhal]

In D149259#4317788, @steakhal wrote:

We only had a single new issue after this patch. This is well within what I would be comfortable with. I'll investigate the case anyway. It's likely something flaky.

It did not reproduce, so it was a fluke.

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

343–345

FYI, you can unconditionally cast it. The assertion wouldn't fire - at least it didn't for us.

[donat.nagy]

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

343–345

I only noticed this after merging my change, but this won't be relevant, because the followup commits will completely restructure this part of the code.

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

public:
   void checkLocation(SVal l, bool isLoad, const Stmt *S,
                      CheckerContext &C) const;
 };
 
 // FIXME: Eventually replace RegionRawOffset with this class.
 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>(); }
+  NonLoc getByteOffset() const { return byteOffset; }
   const SubRegion *getRegion() const { return baseRegion; }
 
-  static RegionRawOffsetV2 computeOffset(ProgramStateRef state,
-                                         SValBuilder &svalBuilder,
-                                         SVal location);
+  static std::optional<RegionRawOffsetV2>
+  computeOffset(ProgramStateRef State, SValBuilder &SVB, SVal Location);
 
   void dump() const;
   void dumpToStream(raw_ostream &os) const;
 };
 }
 
 // TODO: once the constraint manager is smart enough to handle non simplified
 // symbolic expressions remove this function. Note that this can not be used in
void ArrayBoundCheckerV2::checkLocation(SVal location, bool isLoad,
   // accurate reports would be confusing for the users, just disable reports
   // from these macros:
   if (isFromCtypeMacro(LoadS, checkerContext.getASTContext()))
     return;
 
   ProgramStateRef state = checkerContext.getState();
 
   SValBuilder &svalBuilder = checkerContext.getSValBuilder();
-  const RegionRawOffsetV2 &rawOffset =
+  const std::optional<RegionRawOffsetV2> &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<UnknownSpaceRegion>(SR)) {
     // A pointer to UnknownSpaceRegion may point to the middle of
     // an allocated region.
 
     auto [state_precedesLowerBound, state_withinLowerBound] =
         compareValueToThreshold(state, ByteOffset,
                                 svalBuilder.makeZeroArrayIndex(), svalBuilder);
 
     if (state_precedesLowerBound && !state_withinLowerBound) {
       // We know that the index definitely precedes the lower bound.
       reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes);
       return;
     }
 
     if (state_withinLowerBound)
       state = state_withinLowerBound;
   }
 
   // CHECK UPPER BOUND
   DefinedOrUnknownSVal Size =
-      getDynamicExtent(state, rawOffset.getRegion(), svalBuilder);
+      getDynamicExtent(state, RawOffset->getRegion(), svalBuilder);
   if (auto KnownSize = Size.getAs<NonLoc>()) {
     auto [state_withinUpperBound, state_exceedsUpperBound] =
         compareValueToThreshold(state, ByteOffset, *KnownSize, svalBuilder);
 
     if (state_exceedsUpperBound) {
       if (!state_withinUpperBound) {
         // We know that the index definitely exceeds the upper bound.
         reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes);

 LLVM_DUMP_METHOD void RegionRawOffsetV2::dump() const {
   dumpToStream(llvm::errs());
 }
 
 void RegionRawOffsetV2::dumpToStream(raw_ostream &os) const {
   os << "raw_offset_v2{" << getRegion() << ',' << getByteOffset() << '}';
 }
 #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<NonLoc>(),
-                                 y.castAs<NonLoc>(),
-                                 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<SubRegion>(region)) {
-          if (auto Offset = getValue(offset, svalBuilder).getAs<NonLoc>())
-            return RegionRawOffsetV2(subReg, *Offset);
-        }
-        return RegionRawOffsetV2();
-      }
-      case MemRegion::ElementRegionKind: {
-        const ElementRegion *elemReg = cast<ElementRegion>(region);
-        SVal index = elemReg->getIndex();
-        if (!isa<NonLoc>(index))
-          return RegionRawOffsetV2();
-        QualType elemType = elemReg->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<NonLoc>(),
-                          astContext.getTypeSizeInChars(elemType),
-                          svalBuilder),
-                          svalBuilder);
+/// 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>
+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<NonLoc>();
+  };
 
-        if (offset.isUnknownOrUndef())
-          return RegionRawOffsetV2();
+  const MemRegion *Region = Location.getAsRegion();
+  NonLoc Offset = SVB.makeZeroArrayIndex();
 
-        region = elemReg->getSuperRegion();
+  while (Region) {
+    if (const auto *ERegion = dyn_cast<ElementRegion>(Region)) {
+      if (const auto Index = ERegion->getIndex().getAs<NonLoc>()) {
+        QualType ElemType = ERegion->getElementType();
+        // If the element is an incomplete type, go no further.
+        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;
           }
         }
       }
-  return RegionRawOffsetV2();
+    } else if (const auto *SRegion = dyn_cast<SubRegion>(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 {<Region>, 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 std::nullopt;
 }
 
 void ento::registerArrayBoundCheckerV2(CheckerManager &mgr) {
   mgr.registerChecker<ArrayBoundCheckerV2>();
 }
 
 bool ento::shouldRegisterArrayBoundCheckerV2(const CheckerManager &mgr) {
   return true;
 }