Export clang-format16 via ydblib project

6e6be3a95868fde888d801b7590af4044049563f

1 files changed, 181 insertions, 0 deletions

diff --git a/contrib/libs/clang16/lib/StaticAnalyzer/Checkers/STLAlgorithmModeling.cpp b/contrib/libs/clang16/lib/StaticAnalyzer/Checkers/STLAlgorithmModeling.cpp
new file mode 100644
index 0000000000..e9d5d306cc
--- /dev/null
+++ b/contrib/libs/clang16/lib/StaticAnalyzer/Checkers/STLAlgorithmModeling.cpp
@@ -0,0 +1,181 @@
+//===-- STLAlgorithmModeling.cpp -----------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Models STL algorithms.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+
+#include "Iterator.h"
+
+using namespace clang;
+using namespace ento;
+using namespace iterator;
+
+namespace {
+
+class STLAlgorithmModeling : public Checker<eval::Call> {
+  bool evalFind(CheckerContext &C, const CallExpr *CE) const;
+
+  void Find(CheckerContext &C, const CallExpr *CE, unsigned paramNum) const;
+
+  using FnCheck = bool (STLAlgorithmModeling::*)(CheckerContext &,
+                                                const CallExpr *) const;
+
+  const CallDescriptionMap<FnCheck> Callbacks = {
+    {{{"std", "find"}, 3}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "find"}, 4}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "find_if"}, 3}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "find_if"}, 4}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "find_if_not"}, 3}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "find_if_not"}, 4}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "find_first_of"}, 4}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "find_first_of"}, 5}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "find_first_of"}, 6}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "find_end"}, 4}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "find_end"}, 5}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "find_end"}, 6}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "lower_bound"}, 3}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "lower_bound"}, 4}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "upper_bound"}, 3}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "upper_bound"}, 4}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "search"}, 3}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "search"}, 4}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "search"}, 5}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "search"}, 6}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "search_n"}, 4}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "search_n"}, 5}, &STLAlgorithmModeling::evalFind},
+    {{{"std", "search_n"}, 6}, &STLAlgorithmModeling::evalFind},
+  };
+
+public:
+  STLAlgorithmModeling() = default;
+
+  bool AggressiveStdFindModeling;
+
+  bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+}; //
+
+bool STLAlgorithmModeling::evalCall(const CallEvent &Call,
+                                    CheckerContext &C) const {
+  const auto *CE = dyn_cast_or_null<CallExpr>(Call.getOriginExpr());
+  if (!CE)
+    return false;
+
+  const FnCheck *Handler = Callbacks.lookup(Call);
+  if (!Handler)
+    return false;
+
+  return (this->**Handler)(C, CE);
+}
+
+bool STLAlgorithmModeling::evalFind(CheckerContext &C,
+                                    const CallExpr *CE) const {
+  // std::find()-like functions either take their primary range in the first
+  // two parameters, or if the first parameter is "execution policy" then in
+  // the second and third. This means that the second parameter must always be
+  // an iterator.
+  if (!isIteratorType(CE->getArg(1)->getType()))
+    return false;
+
+  // If no "execution policy" parameter is used then the first argument is the
+  // beginning of the range.
+  if (isIteratorType(CE->getArg(0)->getType())) {
+    Find(C, CE, 0);
+    return true;
+  }
+
+  // If "execution policy" parameter is used then the second argument is the
+  // beginning of the range.
+  if (isIteratorType(CE->getArg(2)->getType())) {
+    Find(C, CE, 1);
+    return true;
+  }
+
+  return false;
+}
+
+void STLAlgorithmModeling::Find(CheckerContext &C, const CallExpr *CE,
+                                unsigned paramNum) const {
+  auto State = C.getState();
+  auto &SVB = C.getSValBuilder();
+  const auto *LCtx = C.getLocationContext();
+
+  SVal RetVal = SVB.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
+  SVal Param = State->getSVal(CE->getArg(paramNum), LCtx);
+
+  auto StateFound = State->BindExpr(CE, LCtx, RetVal);
+
+  // If we have an iterator position for the range-begin argument then we can
+  // assume that in case of successful search the position of the found element
+  // is not ahead of it.
+  // FIXME: Reverse iterators
+  const auto *Pos = getIteratorPosition(State, Param);
+  if (Pos) {
+    StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(),
+                                        CE, LCtx, C.blockCount());
+    const auto *NewPos = getIteratorPosition(StateFound, RetVal);
+    assert(NewPos && "Failed to create new iterator position.");
+
+    SVal GreaterOrEqual = SVB.evalBinOp(StateFound, BO_GE,
+                                        nonloc::SymbolVal(NewPos->getOffset()),
+                                        nonloc::SymbolVal(Pos->getOffset()),
+                                        SVB.getConditionType());
+    assert(isa<DefinedSVal>(GreaterOrEqual) &&
+           "Symbol comparison must be a `DefinedSVal`");
+    StateFound = StateFound->assume(GreaterOrEqual.castAs<DefinedSVal>(), true);
+  }
+
+  Param = State->getSVal(CE->getArg(paramNum + 1), LCtx);
+
+  // If we have an iterator position for the range-end argument then we can
+  // assume that in case of successful search the position of the found element
+  // is ahead of it.
+  // FIXME: Reverse iterators
+  Pos = getIteratorPosition(State, Param);
+  if (Pos) {
+    StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(),
+                                        CE, LCtx, C.blockCount());
+    const auto *NewPos = getIteratorPosition(StateFound, RetVal);
+    assert(NewPos && "Failed to create new iterator position.");
+
+    SVal Less = SVB.evalBinOp(StateFound, BO_LT,
+                              nonloc::SymbolVal(NewPos->getOffset()),
+                              nonloc::SymbolVal(Pos->getOffset()),
+                              SVB.getConditionType());
+    assert(isa<DefinedSVal>(Less) &&
+           "Symbol comparison must be a `DefinedSVal`");
+    StateFound = StateFound->assume(Less.castAs<DefinedSVal>(), true);
+  }
+
+  C.addTransition(StateFound);
+
+  if (AggressiveStdFindModeling) {
+    auto StateNotFound = State->BindExpr(CE, LCtx, Param);
+    C.addTransition(StateNotFound);
+  }
+}
+
+} // namespace
+
+void ento::registerSTLAlgorithmModeling(CheckerManager &Mgr) {
+  auto *Checker = Mgr.registerChecker<STLAlgorithmModeling>();
+  Checker->AggressiveStdFindModeling =
+      Mgr.getAnalyzerOptions().getCheckerBooleanOption(Checker,
+                                                  "AggressiveStdFindModeling");
+}
+
+bool ento::shouldRegisterSTLAlgorithmModeling(const CheckerManager &mgr) {
+  return true;
+}
+