//= CStringChecker.cpp - Checks calls to C string functions --------*- C++ -*-//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// This defines CStringChecker, which is an assortment of checks on calls

// to functions in <string.h>.

//

//===----------------------------------------------------------------------===//

#include "InterCheckerAPI.h"

#include "clang/Basic/Builtins.h"

#include "clang/Basic/CharInfo.h"

#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"

#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"

#include "clang/StaticAnalyzer/Core/Checker.h"

#include "clang/StaticAnalyzer/Core/CheckerManager.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/ADT/SmallString.h"

#include "llvm/ADT/StringExtras.h"

#include "llvm/Support/raw_ostream.h"

#include <functional>

#include <optional>

using namespace clang;

using namespace ento;

using namespace std::placeholders;

namespace {

struct AnyArgExpr {

  const Expr *Expression;

  unsigned ArgumentIndex;

};

struct SourceArgExpr : AnyArgExpr {};

struct DestinationArgExpr : AnyArgExpr {};

struct SizeArgExpr : AnyArgExpr {};

using ErrorMessage = SmallString<128>;

enum class AccessKind { write, read };

static ErrorMessage createOutOfBoundErrorMsg(StringRef FunctionDescription,

                                             AccessKind Access) {

  ErrorMessage Message;

  llvm::raw_svector_ostream Os(Message);

  // Function classification like: Memory copy function

  Os << toUppercase(FunctionDescription.front())

     << &FunctionDescription.data()[1];

  if (Access == AccessKind::write) {

    Os << " overflows the destination buffer";

  } else { // read access

    Os << " accesses out-of-bound array element";

  }

  return Message;

}

enum class ConcatFnKind { none = 0, strcat = 1, strlcat = 2 };

enum class CharKind { Regular = 0, Wide };

constexpr CharKind CK_Regular = CharKind::Regular;

constexpr CharKind CK_Wide = CharKind::Wide;

static QualType getCharPtrType(ASTContext &Ctx, CharKind CK) {

  return Ctx.getPointerType(CK == CharKind::Regular ? 
Ctx.CharTy751

                                                    : 
Ctx.WideCharTy200
);

}

class CStringChecker : public Checker< eval::Call,

                                         check::PreStmt<DeclStmt>,

                                         check::LiveSymbols,

                                         check::DeadSymbols,

                                         check::RegionChanges

                                         > {

  mutable std::unique_ptr<BugType> BT_Null, BT_Bounds, BT_Overlap,

      BT_NotCString, BT_AdditionOverflow, BT_UninitRead;

  mutable const char *CurrentFunctionDescription = nullptr;

public:

  /// The filter is used to filter out the diagnostics which are not enabled by

  /// the user.

  struct CStringChecksFilter {

    bool CheckCStringNullArg = false;

    bool CheckCStringOutOfBounds = false;

    bool CheckCStringBufferOverlap = false;

    bool CheckCStringNotNullTerm = false;

    bool CheckCStringUninitializedRead = false;

    CheckerNameRef CheckNameCStringNullArg;

    CheckerNameRef CheckNameCStringOutOfBounds;

    CheckerNameRef CheckNameCStringBufferOverlap;

    CheckerNameRef CheckNameCStringNotNullTerm;

    CheckerNameRef CheckNameCStringUninitializedRead;

  };

  CStringChecksFilter Filter;

  static void *getTag() { static int tag; return &tag; }

  bool evalCall(const CallEvent &Call, CheckerContext &C) const;

  void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;

  void checkLiveSymbols(ProgramStateRef state, SymbolReaper &SR) const;

  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;

  ProgramStateRef

    checkRegionChanges(ProgramStateRef state,

                       const InvalidatedSymbols *,

                       ArrayRef<const MemRegion *> ExplicitRegions,

                       ArrayRef<const MemRegion *> Regions,

                       const LocationContext *LCtx,

                       const CallEvent *Call) const;

  using FnCheck = std::function<void(const CStringChecker *, CheckerContext &,

                                     const CallExpr *)>;

  CallDescriptionMap<FnCheck> Callbacks = {

      {{CDF_MaybeBuiltin, {"memcpy"}, 3},

       std::bind(&CStringChecker::evalMemcpy, _1, _2, _3, CK_Regular)},

      {{CDF_MaybeBuiltin, {"wmemcpy"}, 3},

       std::bind(&CStringChecker::evalMemcpy, _1, _2, _3, CK_Wide)},

      {{CDF_MaybeBuiltin, {"mempcpy"}, 3},

       std::bind(&CStringChecker::evalMempcpy, _1, _2, _3, CK_Regular)},

      {{CDF_None, {"wmempcpy"}, 3},

       std::bind(&CStringChecker::evalMempcpy, _1, _2, _3, CK_Wide)},

      {{CDF_MaybeBuiltin, {"memcmp"}, 3},

       std::bind(&CStringChecker::evalMemcmp, _1, _2, _3, CK_Regular)},

      {{CDF_MaybeBuiltin, {"wmemcmp"}, 3},

       std::bind(&CStringChecker::evalMemcmp, _1, _2, _3, CK_Wide)},

      {{CDF_MaybeBuiltin, {"memmove"}, 3},

       std::bind(&CStringChecker::evalMemmove, _1, _2, _3, CK_Regular)},

      {{CDF_MaybeBuiltin, {"wmemmove"}, 3},

       std::bind(&CStringChecker::evalMemmove, _1, _2, _3, CK_Wide)},

      {{CDF_MaybeBuiltin, {"memset"}, 3}, &CStringChecker::evalMemset},

      {{CDF_MaybeBuiltin, {"explicit_memset"}, 3}, &CStringChecker::evalMemset},

      {{CDF_MaybeBuiltin, {"strcpy"}, 2}, &CStringChecker::evalStrcpy},

      {{CDF_MaybeBuiltin, {"strncpy"}, 3}, &CStringChecker::evalStrncpy},

      {{CDF_MaybeBuiltin, {"stpcpy"}, 2}, &CStringChecker::evalStpcpy},

      {{CDF_MaybeBuiltin, {"strlcpy"}, 3}, &CStringChecker::evalStrlcpy},

      {{CDF_MaybeBuiltin, {"strcat"}, 2}, &CStringChecker::evalStrcat},

      {{CDF_MaybeBuiltin, {"strncat"}, 3}, &CStringChecker::evalStrncat},

      {{CDF_MaybeBuiltin, {"strlcat"}, 3}, &CStringChecker::evalStrlcat},

      {{CDF_MaybeBuiltin, {"strlen"}, 1}, &CStringChecker::evalstrLength},

      {{CDF_MaybeBuiltin, {"wcslen"}, 1}, &CStringChecker::evalstrLength},

      {{CDF_MaybeBuiltin, {"strnlen"}, 2}, &CStringChecker::evalstrnLength},

      {{CDF_MaybeBuiltin, {"wcsnlen"}, 2}, &CStringChecker::evalstrnLength},

      {{CDF_MaybeBuiltin, {"strcmp"}, 2}, &CStringChecker::evalStrcmp},

      {{CDF_MaybeBuiltin, {"strncmp"}, 3}, &CStringChecker::evalStrncmp},

      {{CDF_MaybeBuiltin, {"strcasecmp"}, 2}, &CStringChecker::evalStrcasecmp},

      {{CDF_MaybeBuiltin, {"strncasecmp"}, 3},

       &CStringChecker::evalStrncasecmp},

      {{CDF_MaybeBuiltin, {"strsep"}, 2}, &CStringChecker::evalStrsep},

      {{CDF_MaybeBuiltin, {"bcopy"}, 3}, &CStringChecker::evalBcopy},

      {{CDF_MaybeBuiltin, {"bcmp"}, 3},

       std::bind(&CStringChecker::evalMemcmp, _1, _2, _3, CK_Regular)},

      {{CDF_MaybeBuiltin, {"bzero"}, 2}, &CStringChecker::evalBzero},

      {{CDF_MaybeBuiltin, {"explicit_bzero"}, 2}, &CStringChecker::evalBzero},

      {{CDF_MaybeBuiltin, {"sprintf"}, 2}, &CStringChecker::evalSprintf},

      {{CDF_MaybeBuiltin, {"snprintf"}, 2}, &CStringChecker::evalSnprintf},

  };

  // These require a bit of special handling.

  CallDescription StdCopy{{"std", "copy"}, 3},

      StdCopyBackward{{"std", "copy_backward"}, 3};

  FnCheck identifyCall(const CallEvent &Call, CheckerContext &C) const;

  void evalMemcpy(CheckerContext &C, const CallExpr *CE, CharKind CK) const;

  void evalMempcpy(CheckerContext &C, const CallExpr *CE, CharKind CK) const;

  void evalMemmove(CheckerContext &C, const CallExpr *CE, CharKind CK) const;

  void evalBcopy(CheckerContext &C, const CallExpr *CE) const;

  void evalCopyCommon(CheckerContext &C, const CallExpr *CE,

                      ProgramStateRef state, SizeArgExpr Size,

                      DestinationArgExpr Dest, SourceArgExpr Source,

                      bool Restricted, bool IsMempcpy, CharKind CK) const;

  void evalMemcmp(CheckerContext &C, const CallExpr *CE, CharKind CK) const;

  void evalstrLength(CheckerContext &C, const CallExpr *CE) const;

  void evalstrnLength(CheckerContext &C, const CallExpr *CE) const;

  void evalstrLengthCommon(CheckerContext &C,

                           const CallExpr *CE,

                           bool IsStrnlen = false) const;

  void evalStrcpy(CheckerContext &C, const CallExpr *CE) const;

  void evalStrncpy(CheckerContext &C, const CallExpr *CE) const;

  void evalStpcpy(CheckerContext &C, const CallExpr *CE) const;

  void evalStrlcpy(CheckerContext &C, const CallExpr *CE) const;

  void evalStrcpyCommon(CheckerContext &C, const CallExpr *CE, bool ReturnEnd,

                        bool IsBounded, ConcatFnKind appendK,

                        bool returnPtr = true) const;

  void evalStrcat(CheckerContext &C, const CallExpr *CE) const;

  void evalStrncat(CheckerContext &C, const CallExpr *CE) const;

  void evalStrlcat(CheckerContext &C, const CallExpr *CE) const;

  void evalStrcmp(CheckerContext &C, const CallExpr *CE) const;

  void evalStrncmp(CheckerContext &C, const CallExpr *CE) const;

  void evalStrcasecmp(CheckerContext &C, const CallExpr *CE) const;

  void evalStrncasecmp(CheckerContext &C, const CallExpr *CE) const;

  void evalStrcmpCommon(CheckerContext &C,

                        const CallExpr *CE,

                        bool IsBounded = false,

                        bool IgnoreCase = false) const;

  void evalStrsep(CheckerContext &C, const CallExpr *CE) const;

  void evalStdCopy(CheckerContext &C, const CallExpr *CE) const;

  void evalStdCopyBackward(CheckerContext &C, const CallExpr *CE) const;

  void evalStdCopyCommon(CheckerContext &C, const CallExpr *CE) const;

  void evalMemset(CheckerContext &C, const CallExpr *CE) const;

  void evalBzero(CheckerContext &C, const CallExpr *CE) const;

  void evalSprintf(CheckerContext &C, const CallExpr *CE) const;

  void evalSnprintf(CheckerContext &C, const CallExpr *CE) const;

  void evalSprintfCommon(CheckerContext &C, const CallExpr *CE, bool IsBounded,

                         bool IsBuiltin) const;

  // Utility methods

  std::pair<ProgramStateRef , ProgramStateRef >

  static assumeZero(CheckerContext &C,

                    ProgramStateRef state, SVal V, QualType Ty);

  static ProgramStateRef setCStringLength(ProgramStateRef state,

                                              const MemRegion *MR,

                                              SVal strLength);

  static SVal getCStringLengthForRegion(CheckerContext &C,

                                        ProgramStateRef &state,

                                        const Expr *Ex,

                                        const MemRegion *MR,

                                        bool hypothetical);

  SVal getCStringLength(CheckerContext &C,

                        ProgramStateRef &state,

                        const Expr *Ex,

                        SVal Buf,

                        bool hypothetical = false) const;

  const StringLiteral *getCStringLiteral(CheckerContext &C,

                                         ProgramStateRef &state,

                                         const Expr *expr,

                                         SVal val) const;

  /// Invalidate the destination buffer determined by characters copied.

  static ProgramStateRef

  invalidateDestinationBufferBySize(CheckerContext &C, ProgramStateRef S,

                                    const Expr *BufE, SVal BufV, SVal SizeV,

                                    QualType SizeTy);

  /// Operation never overflows, do not invalidate the super region.

  static ProgramStateRef invalidateDestinationBufferNeverOverflows(

      CheckerContext &C, ProgramStateRef S, const Expr *BufE, SVal BufV);

  /// We do not know whether the operation can overflow (e.g. size is unknown),

  /// invalidate the super region and escape related pointers.

  static ProgramStateRef invalidateDestinationBufferAlwaysEscapeSuperRegion(

      CheckerContext &C, ProgramStateRef S, const Expr *BufE, SVal BufV);

  /// Invalidate the source buffer for escaping pointers.

  static ProgramStateRef invalidateSourceBuffer(CheckerContext &C,

                                                ProgramStateRef S,

                                                const Expr *BufE, SVal BufV);

  /// @param InvalidationTraitOperations Determine how to invlidate the

  /// MemRegion by setting the invalidation traits. Return true to cause pointer

  /// escape, or false otherwise.

  static ProgramStateRef invalidateBufferAux(

      CheckerContext &C, ProgramStateRef State, const Expr *Ex, SVal V,

      llvm::function_ref<bool(RegionAndSymbolInvalidationTraits &,

                              const MemRegion *)>

          InvalidationTraitOperations);

  static bool SummarizeRegion(raw_ostream &os, ASTContext &Ctx,

                              const MemRegion *MR);

  static bool memsetAux(const Expr *DstBuffer, SVal CharE,

                        const Expr *Size, CheckerContext &C,

                        ProgramStateRef &State);

  // Re-usable checks

  ProgramStateRef checkNonNull(CheckerContext &C, ProgramStateRef State,

                               AnyArgExpr Arg, SVal l) const;

  ProgramStateRef CheckLocation(CheckerContext &C, ProgramStateRef state,

                                AnyArgExpr Buffer, SVal Element,

                                AccessKind Access,

                                CharKind CK = CharKind::Regular) const;

  ProgramStateRef CheckBufferAccess(CheckerContext &C, ProgramStateRef State,

                                    AnyArgExpr Buffer, SizeArgExpr Size,

                                    AccessKind Access,

                                    CharKind CK = CharKind::Regular) const;

  ProgramStateRef CheckOverlap(CheckerContext &C, ProgramStateRef state,

                               SizeArgExpr Size, AnyArgExpr First,

                               AnyArgExpr Second,

                               CharKind CK = CharKind::Regular) const;

  void emitOverlapBug(CheckerContext &C,

                      ProgramStateRef state,

                      const Stmt *First,

                      const Stmt *Second) const;

  void emitNullArgBug(CheckerContext &C, ProgramStateRef State, const Stmt *S,

                      StringRef WarningMsg) const;

  void emitOutOfBoundsBug(CheckerContext &C, ProgramStateRef State,

                          const Stmt *S, StringRef WarningMsg) const;

  void emitNotCStringBug(CheckerContext &C, ProgramStateRef State,

                         const Stmt *S, StringRef WarningMsg) const;

  void emitAdditionOverflowBug(CheckerContext &C, ProgramStateRef State) const;

  void emitUninitializedReadBug(CheckerContext &C, ProgramStateRef State,

                             const Expr *E) const;

  ProgramStateRef checkAdditionOverflow(CheckerContext &C,

                                            ProgramStateRef state,

                                            NonLoc left,

                                            NonLoc right) const;

  // Return true if the destination buffer of the copy function may be in bound.

  // Expects SVal of Size to be positive and unsigned.

  // Expects SVal of FirstBuf to be a FieldRegion.

  static bool isFirstBufInBound(CheckerContext &C, ProgramStateRef State,

                                SVal BufVal, QualType BufTy, SVal LengthVal,

                                QualType LengthTy);

};

} //end anonymous namespace

REGISTER_MAP_WITH_PROGRAMSTATE(CStringLength, const MemRegion *, SVal)

//===----------------------------------------------------------------------===//

// Individual checks and utility methods.

//===----------------------------------------------------------------------===//

std::pair<ProgramStateRef , ProgramStateRef >

CStringChecker::assumeZero(CheckerContext &C, ProgramStateRef state, SVal V,

                           QualType Ty) {

  std::optional<DefinedSVal> val = V.getAs<DefinedSVal>();

  if (!val)

    return std::pair<ProgramStateRef , ProgramStateRef >(state, state);

  SValBuilder &svalBuilder = C.getSValBuilder();

  DefinedOrUnknownSVal zero = svalBuilder.makeZeroVal(Ty);

  return state->assume(svalBuilder.evalEQ(state, *val, zero));

}

ProgramStateRef CStringChecker::checkNonNull(CheckerContext &C,

                                             ProgramStateRef State,

                                             AnyArgExpr Arg, SVal l) const {

  // If a previous check has failed, propagate the failure.

  if (!State)

    return nullptr;

  ProgramStateRef stateNull, stateNonNull;

  std::tie(stateNull, stateNonNull) =

      assumeZero(C, State, l, Arg.Expression->getType());

  if (stateNull && 
!stateNonNull619
) {

    if (Filter.CheckCStringNullArg) {

      SmallString<80> buf;

      llvm::raw_svector_ostream OS(buf);

      assert(CurrentFunctionDescription);

      OS << "Null pointer passed as " << (Arg.ArgumentIndex + 1)

         << llvm::getOrdinalSuffix(Arg.ArgumentIndex + 1) << " argument to "

         << CurrentFunctionDescription;

      emitNullArgBug(C, stateNull, Arg.Expression, OS.str());

    }

    return nullptr;

  }

  // From here on, assume that the value is non-null.

  assert(stateNonNull);

  return stateNonNull;

}

// FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor?

ProgramStateRef CStringChecker::CheckLocation(CheckerContext &C,

                                              ProgramStateRef state,

                                              AnyArgExpr Buffer, SVal Element,

                                              AccessKind Access,

                                              CharKind CK) const {

  // If a previous check has failed, propagate the failure.

  if (!state)

    return nullptr;

  // Check for out of bound array element access.

  const MemRegion *R = Element.getAsRegion();

  if (!R)

    return state;

  const auto *ER = dyn_cast<ElementRegion>(R);

  if (!ER)

    return state;

  SValBuilder &svalBuilder = C.getSValBuilder();

  ASTContext &Ctx = svalBuilder.getContext();

  // Get the index of the accessed element.

  NonLoc Idx = ER->getIndex();

  if (CK == CharKind::Regular) {

    if (ER->getValueType() != Ctx.CharTy)

      return state;

  } else {

    if (ER->getValueType() != Ctx.WideCharTy)

      return state;

    QualType SizeTy = Ctx.getSizeType();

    NonLoc WideSize =

        svalBuilder

            .makeIntVal(Ctx.getTypeSizeInChars(Ctx.WideCharTy).getQuantity(),

                        SizeTy)

            .castAs<NonLoc>();

    SVal Offset = svalBuilder.evalBinOpNN(state, BO_Mul, Idx, WideSize, SizeTy);

    if (Offset.isUnknown())

      return state;

    Idx = Offset.castAs<NonLoc>();

  }

  // Get the size of the array.

  const auto *superReg = cast<SubRegion>(ER->getSuperRegion());

  DefinedOrUnknownSVal Size =

      getDynamicExtent(state, superReg, C.getSValBuilder());

  ProgramStateRef StInBound, StOutBound;

  std::tie(StInBound, StOutBound) = state->assumeInBoundDual(Idx, Size);

  if (StOutBound && 
!StInBound372
) {

    // These checks are either enabled by the CString out-of-bounds checker

    // explicitly or implicitly by the Malloc checker.

    // In the latter case we only do modeling but do not emit warning.

    if (!Filter.CheckCStringOutOfBounds)

      return nullptr;

    // Emit a bug report.

    ErrorMessage Message =

        createOutOfBoundErrorMsg(CurrentFunctionDescription, Access);

    emitOutOfBoundsBug(C, StOutBound, Buffer.Expression, Message);

    return nullptr;

  }

  // Ensure that we wouldn't read uninitialized value.

  if (Access == AccessKind::read) {

    if (Filter.CheckCStringUninitializedRead &&

        
StInBound->getSVal(ER).isUndef()15
) {

      emitUninitializedReadBug(C, StInBound, Buffer.Expression);

      return nullptr;

    }

  }

  // Array bound check succeeded.  From this point forward the array bound

  // should always succeed.

  return StInBound;

}

ProgramStateRef

CStringChecker::CheckBufferAccess(CheckerContext &C, ProgramStateRef State,

                                  AnyArgExpr Buffer, SizeArgExpr Size,

                                  AccessKind Access, CharKind CK) const {

  // If a previous check has failed, propagate the failure.

  if (!State)

    return nullptr;

  SValBuilder &svalBuilder = C.getSValBuilder();

  ASTContext &Ctx = svalBuilder.getContext();

  QualType SizeTy = Size.Expression->getType();

  QualType PtrTy = getCharPtrType(Ctx, CK);

  // Check that the first buffer is non-null.

  SVal BufVal = C.getSVal(Buffer.Expression);

  State = checkNonNull(C, State, Buffer, BufVal);

  if (!State)

    return nullptr;

  // If out-of-bounds checking is turned off, skip the rest.

  if (!Filter.CheckCStringOutOfBounds)

    return State;

  SVal BufStart =

      svalBuilder.evalCast(BufVal, PtrTy, Buffer.Expression->getType());

  // Check if the first byte of the buffer is accessible.

  State = CheckLocation(C, State, Buffer, BufStart, Access, CK);

  if (!State)

    return nullptr;

  // Get the access length and make sure it is known.

  // FIXME: This assumes the caller has already checked that the access length

  // is positive. And that it's unsigned.

  SVal LengthVal = C.getSVal(Size.Expression);

  std::optional<NonLoc> Length = LengthVal.getAs<NonLoc>();

  if (!Length)

    return State;

  // Compute the offset of the last element to be accessed: size-1.

  NonLoc One = svalBuilder.makeIntVal(1, SizeTy).castAs<NonLoc>();

  SVal Offset = svalBuilder.evalBinOpNN(State, BO_Sub, *Length, One, SizeTy);

  if (Offset.isUnknown())

    return nullptr;

  NonLoc LastOffset = Offset.castAs<NonLoc>();

  // Check that the first buffer is sufficiently long.

  if (std::optional<Loc> BufLoc = BufStart.getAs<Loc>()) {

    SVal BufEnd =

        svalBuilder.evalBinOpLN(State, BO_Add, *BufLoc, LastOffset, PtrTy);

    State = CheckLocation(C, State, Buffer, BufEnd, Access, CK);

    // If the buffer isn't large enough, abort.

    if (!State)

      return nullptr;

  }

  // Large enough or not, return this state!

  return State;

}

ProgramStateRef CStringChecker::CheckOverlap(CheckerContext &C,

                                             ProgramStateRef state,

                                             SizeArgExpr Size, AnyArgExpr First,

                                             AnyArgExpr Second,

                                             CharKind CK) const {

  if (!Filter.CheckCStringBufferOverlap)

    return state;

  // Do a simple check for overlap: if the two arguments are from the same

  // buffer, see if the end of the first is greater than the start of the second

  // or vice versa.

  // If a previous check has failed, propagate the failure.

  if (!state)

    return nullptr;

  ProgramStateRef stateTrue, stateFalse;

  // Assume different address spaces cannot overlap.

  if (First.Expression->getType()->getPointeeType().getAddressSpace() !=

      Second.Expression->getType()->getPointeeType().getAddressSpace())

    return state;

  // Get the buffer values and make sure they're known locations.

  const LocationContext *LCtx = C.getLocationContext();

  SVal firstVal = state->getSVal(First.Expression, LCtx);

  SVal secondVal = state->getSVal(Second.Expression, LCtx);

  std::optional<Loc> firstLoc = firstVal.getAs<Loc>();

  if (!firstLoc)

    return state;

  std::optional<Loc> secondLoc = secondVal.getAs<Loc>();

  if (!secondLoc)

    return state;

  // Are the two values the same?

  SValBuilder &svalBuilder = C.getSValBuilder();

  std::tie(stateTrue, stateFalse) =

      state->assume(svalBuilder.evalEQ(state, *firstLoc, *secondLoc));

  if (stateTrue && 
!stateFalse77
) {

    // If the values are known to be equal, that's automatically an overlap.

    emitOverlapBug(C, stateTrue, First.Expression, Second.Expression);

    return nullptr;

  }

  // assume the two expressions are not equal.

  assert(stateFalse);

  state = stateFalse;

  // Which value comes first?

  QualType cmpTy = svalBuilder.getConditionType();

  SVal reverse =

      svalBuilder.evalBinOpLL(state, BO_GT, *firstLoc, *secondLoc, cmpTy);

  std::optional<DefinedOrUnknownSVal> reverseTest =

      reverse.getAs<DefinedOrUnknownSVal>();

  if (!reverseTest)

    return state;

  std::tie(stateTrue, stateFalse) = state->assume(*reverseTest);

  if (stateTrue) {

    if (stateFalse) {

      // If we don't know which one comes first, we can't perform this test.

      return state;

    } else {

      // Switch the values so that firstVal is before secondVal.

      std::swap(firstLoc, secondLoc);

      // Switch the Exprs as well, so that they still correspond.

      std::swap(First, Second);

    }

  }

  // Get the length, and make sure it too is known.

  SVal LengthVal = state->getSVal(Size.Expression, LCtx);

  std::optional<NonLoc> Length = LengthVal.getAs<NonLoc>();

  if (!Length)

    return state;

  // Convert the first buffer's start address to char*.

  // Bail out if the cast fails.

  ASTContext &Ctx = svalBuilder.getContext();

  QualType CharPtrTy = getCharPtrType(Ctx, CK);

  SVal FirstStart =

      svalBuilder.evalCast(*firstLoc, CharPtrTy, First.Expression->getType());

  std::optional<Loc> FirstStartLoc = FirstStart.getAs<Loc>();

  if (!FirstStartLoc)

    return state;

  // Compute the end of the first buffer. Bail out if THAT fails.

  SVal FirstEnd = svalBuilder.evalBinOpLN(state, BO_Add, *FirstStartLoc,

                                          *Length, CharPtrTy);

  std::optional<Loc> FirstEndLoc = FirstEnd.getAs<Loc>();

  if (!FirstEndLoc)

    return state;

  // Is the end of the first buffer past the start of the second buffer?

  SVal Overlap =

      svalBuilder.evalBinOpLL(state, BO_GT, *FirstEndLoc, *secondLoc, cmpTy);

  std::optional<DefinedOrUnknownSVal> OverlapTest =

      Overlap.getAs<DefinedOrUnknownSVal>();

  if (!OverlapTest)

    return state;

  std::tie(stateTrue, stateFalse) = state->assume(*OverlapTest);

  if (stateTrue && 
!stateFalse29
) {

    // Overlap!

    emitOverlapBug(C, stateTrue, First.Expression, Second.Expression);

    return nullptr;

  }

  // assume the two expressions don't overlap.

  assert(stateFalse);

  return stateFalse;

}

void CStringChecker::emitOverlapBug(CheckerContext &C, ProgramStateRef state,

                                  const Stmt *First, const Stmt *Second) const {

  ExplodedNode *N = C.generateErrorNode(state);

  if (!N)

    return;

  if (!BT_Overlap)

    BT_Overlap.reset(new BugType(Filter.CheckNameCStringBufferOverlap,

                                 categories::UnixAPI, "Improper arguments"));

  // Generate a report for this bug.

  auto report = std::make_unique<PathSensitiveBugReport>(

      *BT_Overlap, "Arguments must not be overlapping buffers", N);

  report->addRange(First->getSourceRange());

  report->addRange(Second->getSourceRange());

  C.emitReport(std::move(report));

}

void CStringChecker::emitNullArgBug(CheckerContext &C, ProgramStateRef State,

                                    const Stmt *S, StringRef WarningMsg) const {

  if (ExplodedNode *N = C.generateErrorNode(State)) {

    if (!BT_Null) {

      // FIXME: This call uses the string constant 'categories::UnixAPI' as the

      // description of the bug; it should be replaced by a real description.

      BT_Null.reset(

          new BugType(Filter.CheckNameCStringNullArg, categories::UnixAPI));

    }

    auto Report =

        std::make_unique<PathSensitiveBugReport>(*BT_Null, WarningMsg, N);

    Report->addRange(S->getSourceRange());

    if (const auto *Ex = dyn_cast<Expr>(S))

      bugreporter::trackExpressionValue(N, Ex, *Report);

    C.emitReport(std::move(Report));

  }

}

void CStringChecker::emitUninitializedReadBug(CheckerContext &C,

                                              ProgramStateRef State,

                                              const Expr *E) const {

  if (ExplodedNode *N = C.generateErrorNode(State)) {

    const char *Msg =

        "Bytes string function accesses uninitialized/garbage values";

    if (!BT_UninitRead)

      BT_UninitRead.reset(new BugType(Filter.CheckNameCStringUninitializedRead,

                                      "Accessing unitialized/garbage values"));

    auto Report =

        std::make_unique<PathSensitiveBugReport>(*BT_UninitRead, Msg, N);

    Report->addRange(E->getSourceRange());

    bugreporter::trackExpressionValue(N, E, *Report);

    C.emitReport(std::move(Report));

  }

}

void CStringChecker::emitOutOfBoundsBug(CheckerContext &C,

                                        ProgramStateRef State, const Stmt *S,

                                        StringRef WarningMsg) const {

  if (ExplodedNode *N = C.generateErrorNode(State)) {

    if (!BT_Bounds)

      BT_Bounds.reset(new BugType(Filter.CheckCStringOutOfBounds

                                      ? Filter.CheckNameCStringOutOfBounds

                                      : 
Filter.CheckNameCStringNullArg0
,

                                  "Out-of-bound array access"));

    // FIXME: It would be nice to eventually make this diagnostic more clear,

    // e.g., by referencing the original declaration or by saying *why* this

    // reference is outside the range.

    auto Report =

        std::make_unique<PathSensitiveBugReport>(*BT_Bounds, WarningMsg, N);

    Report->addRange(S->getSourceRange());

    C.emitReport(std::move(Report));

  }

}

void CStringChecker::emitNotCStringBug(CheckerContext &C, ProgramStateRef State,

                                       const Stmt *S,

                                       StringRef WarningMsg) const {

  if (ExplodedNode *N = C.generateNonFatalErrorNode(State)) {

    if (!BT_NotCString) {

      // FIXME: This call uses the string constant 'categories::UnixAPI' as the

      // description of the bug; it should be replaced by a real description.

      BT_NotCString.reset(

          new BugType(Filter.CheckNameCStringNotNullTerm, categories::UnixAPI));

    }

    auto Report =

        std::make_unique<PathSensitiveBugReport>(*BT_NotCString, WarningMsg, N);

    Report->addRange(S->getSourceRange());

    C.emitReport(std::move(Report));

  }

}

void CStringChecker::emitAdditionOverflowBug(CheckerContext &C,

                                             ProgramStateRef State) const {

  if (ExplodedNode *N = C.generateErrorNode(State)) {

    if (!BT_AdditionOverflow) {

      // FIXME: This call uses the word "API" as the description of the bug;

      // it should be replaced by a better error message (if this unlikely

      // situation continues to exist as a separate bug type).

      BT_AdditionOverflow.reset(

          new BugType(Filter.CheckNameCStringOutOfBounds, "API"));

    }

    // This isn't a great error message, but this should never occur in real

    // code anyway -- you'd have to create a buffer longer than a size_t can

    // represent, which is sort of a contradiction.

    const char *WarningMsg =

        "This expression will create a string whose length is too big to "

        "be represented as a size_t";

    auto Report = std::make_unique<PathSensitiveBugReport>(*BT_AdditionOverflow,

                                                           WarningMsg, N);

    C.emitReport(std::move(Report));

  }

}

ProgramStateRef CStringChecker::checkAdditionOverflow(CheckerContext &C,

                                                     ProgramStateRef state,

                                                     NonLoc left,

                                                     NonLoc right) const {

  // If out-of-bounds checking is turned off, skip the rest.

  if (!Filter.CheckCStringOutOfBounds)

    return state;

  // If a previous check has failed, propagate the failure.

  if (!state)

    return nullptr;

  SValBuilder &svalBuilder = C.getSValBuilder();

  BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();

  QualType sizeTy = svalBuilder.getContext().getSizeType();

  const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy);

  NonLoc maxVal = svalBuilder.makeIntVal(maxValInt);

  SVal maxMinusRight;

  if (isa<nonloc::ConcreteInt>(right)) {

    maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, right,

                                                 sizeTy);

  } else {

    // Try switching the operands. (The order of these two assignments is

    // important!)

    maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, left,

                                            sizeTy);

    left = right;

  }

  if (std::optional<NonLoc> maxMinusRightNL = maxMinusRight.getAs<NonLoc>()) {

    QualType cmpTy = svalBuilder.getConditionType();

    // If left > max - right, we have an overflow.

    SVal willOverflow = svalBuilder.evalBinOpNN(state, BO_GT, left,

                                                *maxMinusRightNL, cmpTy);

    ProgramStateRef stateOverflow, stateOkay;

    std::tie(stateOverflow, stateOkay) =

      state->assume(willOverflow.castAs<DefinedOrUnknownSVal>());

    if (stateOverflow && 
!stateOkay0
) {

      // We have an overflow. Emit a bug report.

      emitAdditionOverflowBug(C, stateOverflow);

      return nullptr;

    }

    // From now on, assume an overflow didn't occur.

    assert(stateOkay);

    state = stateOkay;

  }

  return state;

}

ProgramStateRef CStringChecker::setCStringLength(ProgramStateRef state,

                                                const MemRegion *MR,

                                                SVal strLength) {

  assert(!strLength.isUndef() && "Attempt to set an undefined string length");

  MR = MR->StripCasts();

  switch (MR->getKind()) {

  case MemRegion::StringRegionKind:

    // FIXME: This can happen if we strcpy() into a string region. This is

    // undefined [C99 6.4.5p6], but we should still warn about it.

    return state;

  case MemRegion::SymbolicRegionKind:

  case MemRegion::AllocaRegionKind:

  case MemRegion::NonParamVarRegionKind:

  case MemRegion::ParamVarRegionKind:

  case MemRegion::FieldRegionKind:

  case MemRegion::ObjCIvarRegionKind:

    // These are the types we can currently track string lengths for.

    break;

  case MemRegion::ElementRegionKind:

    // FIXME: Handle element regions by upper-bounding the parent region's

    // string length.

    return state;

  default:

    // Other regions (mostly non-data) can't have a reliable C string length.

    // For now, just ignore the change.

    // FIXME: These are rare but not impossible. We should output some kind of

    // warning for things like strcpy((char[]){'a', 0}, "b");

    return state;

  }

  if (strLength.isUnknown())

    return state->remove<CStringLength>(MR);

  return state->set<CStringLength>(MR, strLength);

}

SVal CStringChecker::getCStringLengthForRegion(CheckerContext &C,

                                               ProgramStateRef &state,

                                               const Expr *Ex,

                                               const MemRegion *MR,

                                               bool hypothetical) {

  if (!hypothetical) {

    // If there's a recorded length, go ahead and return it.

    const SVal *Recorded = state->get<CStringLength>(MR);

    if (Recorded)

      return *Recorded;

  }

  // Otherwise, get a new symbol and update the state.

  SValBuilder &svalBuilder = C.getSValBuilder();

  QualType sizeTy = svalBuilder.getContext().getSizeType();

  SVal strLength = svalBuilder.getMetadataSymbolVal(CStringChecker::getTag(),

                                                    MR, Ex, sizeTy,

                                                    C.getLocationContext(),

                                                    C.blockCount());

  if (!hypothetical) {

    if (std::optional<NonLoc> strLn = strLength.getAs<NonLoc>()) {

      // In case of unbounded calls strlen etc bound the range to SIZE_MAX/4

      BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();

      const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy);

      llvm::APSInt fourInt = APSIntType(maxValInt).getValue(4);

      const llvm::APSInt *maxLengthInt = BVF.evalAPSInt(BO_Div, maxValInt,

                                                        fourInt);

      NonLoc maxLength = svalBuilder.makeIntVal(*maxLengthInt);

      SVal evalLength = svalBuilder.evalBinOpNN(state, BO_LE, *strLn,

                                                maxLength, sizeTy);

      state = state->assume(evalLength.castAs<DefinedOrUnknownSVal>(), true);

    }

    state = state->set<CStringLength>(MR, strLength);

  }

  return strLength;

}

SVal CStringChecker::getCStringLength(CheckerContext &C, ProgramStateRef &state,

                                      const Expr *Ex, SVal Buf,

                                      bool hypothetical) const {

  const MemRegion *MR = Buf.getAsRegion();

  if (!MR) {

    // If we can't get a region, see if it's something we /know/ isn't a

    // C string. In the context of locations, the only time we can issue such

    // a warning is for labels.

    if (std::optional<loc::GotoLabel> Label = Buf.getAs<loc::GotoLabel>()) {

      if (Filter.CheckCStringNotNullTerm) {

        SmallString<120> buf;

        llvm::raw_svector_ostream os(buf);

        assert(CurrentFunctionDescription);

        os << "Argument to " << CurrentFunctionDescription

           << " is the address of the label '" << Label->getLabel()->getName()

           << "', which is not a null-terminated string";

        emitNotCStringBug(C, state, Ex, os.str());

      }

      return UndefinedVal();

    }

    // If it's not a region and not a label, give up.

    return UnknownVal();

  }

  // If we have a region, strip casts from it and see if we can figure out

  // its length. For anything we can't figure out, just return UnknownVal.

  MR = MR->StripCasts();

  switch (MR->getKind()) {

  case MemRegion::StringRegionKind: {

    // Modifying the contents of string regions is undefined [C99 6.4.5p6],

    // so we can assume that the byte length is the correct C string length.

    SValBuilder &svalBuilder = C.getSValBuilder();

    QualType sizeTy = svalBuilder.getContext().getSizeType();

    const StringLiteral *strLit = cast<StringRegion>(MR)->getStringLiteral();

    return svalBuilder.makeIntVal(strLit->getLength(), sizeTy);

  }

  case MemRegion::SymbolicRegionKind:

  case MemRegion::AllocaRegionKind:

  case MemRegion::NonParamVarRegionKind:

  case MemRegion::ParamVarRegionKind:

  case MemRegion::FieldRegionKind:

  case MemRegion::ObjCIvarRegionKind:

    return getCStringLengthForRegion(C, state, Ex, MR, hypothetical);

  case MemRegion::CompoundLiteralRegionKind:

    // FIXME: Can we track this? Is it necessary?

    return UnknownVal();

  case MemRegion::ElementRegionKind:

    // FIXME: How can we handle this? It's not good enough to subtract the

    // offset from the base string length; consider "123\x00567" and &a[5].

    return UnknownVal();

  default:

    // Other regions (mostly non-data) can't have a reliable C string length.

    // In this case, an error is emitted and UndefinedVal is returned.

    // The caller should always be prepared to handle this case.

    if (Filter.CheckCStringNotNullTerm) {

      SmallString<120> buf;

      llvm::raw_svector_ostream os(buf);

      assert(CurrentFunctionDescription);

      os << "Argument to " << CurrentFunctionDescription << " is ";

      if (SummarizeRegion(os, C.getASTContext(), MR))

        os << ", which is not a null-terminated string";

      else

        os << "not a null-terminated string";

      emitNotCStringBug(C, state, Ex, os.str());

    }

    return UndefinedVal();

  }

}

const StringLiteral *CStringChecker::getCStringLiteral(CheckerContext &C,

  ProgramStateRef &state, const Expr *expr, SVal val) const {

  // Get the memory region pointed to by the val.

  const MemRegion *bufRegion = val.getAsRegion();

  if (!bufRegion)

    return nullptr;

  // Strip casts off the memory region.

  bufRegion = bufRegion->StripCasts();

  // Cast the memory region to a string region.

  const StringRegion *strRegion= dyn_cast<StringRegion>(bufRegion);

  if (!strRegion)

    return nullptr;

  // Return the actual string in the string region.

  return strRegion->getStringLiteral();

}

bool CStringChecker::isFirstBufInBound(CheckerContext &C, ProgramStateRef State,

                                       SVal BufVal, QualType BufTy,

                                       SVal LengthVal, QualType LengthTy) {

  // If we do not know that the buffer is long enough we return 'true'.

  // Otherwise the parent region of this field region would also get

  // invalidated, which would lead to warnings based on an unknown state.

  if (LengthVal.isUnknown())

    return false;

  // Originally copied from CheckBufferAccess and CheckLocation.

  SValBuilder &SB = C.getSValBuilder();

  ASTContext &Ctx = C.getASTContext();

  QualType PtrTy = Ctx.getPointerType(Ctx.CharTy);

  std::optional<NonLoc> Length = LengthVal.getAs<NonLoc>();

  if (!Length)

    return true; // cf top comment.

  // Compute the offset of the last element to be accessed: size-1.

  NonLoc One = SB.makeIntVal(1, LengthTy).castAs<NonLoc>();

  SVal Offset = SB.evalBinOpNN(State, BO_Sub, *Length, One, LengthTy);

  if (Offset.isUnknown())

    return true; // cf top comment

  NonLoc LastOffset = Offset.castAs<NonLoc>();

  // Check that the first buffer is sufficiently long.

  SVal BufStart = SB.evalCast(BufVal, PtrTy, BufTy);

  std::optional<Loc> BufLoc = BufStart.getAs<Loc>();

  if (!BufLoc)

    return true; // cf top comment.

  SVal BufEnd = SB.evalBinOpLN(State, BO_Add, *BufLoc, LastOffset, PtrTy);

  // Check for out of bound array element access.

  const MemRegion *R = BufEnd.getAsRegion();

  if (!R)

    return true; // cf top comment.

  const ElementRegion *ER = dyn_cast<ElementRegion>(R);

  if (!ER)

    return true; // cf top comment.

  // FIXME: Does this crash when a non-standard definition

  // of a library function is encountered?

  assert(ER->getValueType() == C.getASTContext().CharTy &&

         "isFirstBufInBound should only be called with char* ElementRegions");

  // Get the size of the array.

  const SubRegion *superReg = cast<SubRegion>(ER->getSuperRegion());

  DefinedOrUnknownSVal SizeDV = getDynamicExtent(State, superReg, SB);

  // Get the index of the accessed element.

  DefinedOrUnknownSVal Idx = ER->getIndex().castAs<DefinedOrUnknownSVal>();

  ProgramStateRef StInBound = State->assumeInBound(Idx, SizeDV, true);

  return static_cast<bool>(StInBound);

}

ProgramStateRef CStringChecker::invalidateDestinationBufferBySize(

    CheckerContext &C, ProgramStateRef S, const Expr *BufE, SVal BufV,

    SVal SizeV, QualType SizeTy) {

  auto InvalidationTraitOperations =

      [&C, S, BufTy = BufE->getType(), BufV, SizeV,

       SizeTy](RegionAndSymbolInvalidationTraits &ITraits, const MemRegion *R) {

        // If destination buffer is a field region and access is in bound, do

        // not invalidate its super region.

        if (MemRegion::FieldRegionKind == R->getKind() &&

            
isFirstBufInBound(C, S, BufV, BufTy, SizeV, SizeTy)47
) {

          ITraits.setTrait(

              R,

              RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion);