[analyzer] Self Assignment Checker

[baloghadamsoftware]

Summary

This checker checks copy and move assignment operators whether they are protected against self-assignment. Since C++ core guidelines discourages explicit checking for `&rhs==this` in general we take a different approach: in top-frame analysis we branch the exploded graph for two cases, where &rhs==this and &rhs!=this and let existing checkers (e.g. unix.Malloc) do the rest of the work. It is important that we check all copy and move assignment operator in top frame even if we checked them already since self-assignments may happen undetected even in the same translation unit (e.g. using random indices for an array what may or may not be the same).

[baloghadamsoftware]

Initial comments added to the checker and tests are converted from <CR><LF> (DOS) to <LF> (Unix) format.

[dcoughlin]

Thanks for the patch! This looks like it will catch some nasty bugs.

My comments (inline) are mostly nits. But two are more substantial: (1) you should add a path note where the self-assignment assumption is made explaining the assumption to the user and (2) the potential cost of the eager case split could be high -- can it be mitigated by changing the inlining mode?

lib/StaticAnalyzer/Checkers/SelfAssignmentChecker.cpp

13 ↗

(On Diff #54968)

An interesting part of this checker is that it doesn't actually perform any checks itself. Instead, it helps other checkers finds bugs by causing the analyzer to explore copy and move assignment operators twice: once for when 'this' aliases with the parameter and once for when it may not.

I think it is worth mentioning this explicitly in the comment because it unusual. Most checkers don't work this way.

26 ↗

(On Diff #54968)

What do you think about renaming this class to something like "CXXSelfAssignmentChecker"? I think name is a bit confusing because in Objective-C there is a notion of assigning to self (which is the ObjC equivalent of this).

lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp

435 ↗

(On Diff #54968)

It would be good to add a comment explaining why we re-analyze these methods at the top level.

436 ↗

(On Diff #54968)

The LLVM style is to put spaces after if and around ||. http://llvm.org/docs/CodingStandards.html#spaces-before-parentheses

450 ↗

(On Diff #54968)

One thing I am concerned about is that this will introduce an eager case split, which can be quite expensive. We could potentially mitigate this cost by changing getInliningModeForFunction() to return ExprEngine::Inline_Minimal for the copy and move assignment operators when analyzing them at the top level after they have already been inlined elsewhere. Inline_Minimal would prevent most inlining in these methods and thus reduce cost, but would also reduce coverage (leading to false negatives). Do you have a sense of how often self-assignment issues arise in inlined calls vs. in the operators themselves?

(Also the spacing around && doesn't match LLVM style here.)

test/Analysis/self-assign-unused.cpp

21 ↗

(On Diff #54968)

I think it is important to add a path note saying something like "Assuming '*this' is equal to 'rhs'".

To do this, you can add a new BugReporterVisitor subclass to BugReporterVisitors.h that walks a error path backwards to add the note. There is an example of how to do this in NonLocalizedStringBRVisitor in LocalizationChecker.cpp.

Unlike the localization checker, however, the path note for the self assignment checker will be added to errors generated by *other* checkers, so you should register the new bug report visitor for all reports in GRBugReporter::generatePathDiagnostic() (similar to NilReceiverBRVisitor).

22 ↗

(On Diff #54968)

I think it would be good to add;

clang_analyzer_eval(*this == rhs); // expected-warning{{TRUE}} expected-warning{{UNKNOWN}}

here to explicitly test for the case split. You'll need to add a prototype void clang_analyzer_eval(int); to use this.

26 ↗

(On Diff #54968)

It would be good to also test the move assignment operator.

test/Analysis/self-assign-used.cpp

1 ↗

(On Diff #54968)

Can you combine these into one test file? This way someone updating the tests will know there is only one place to look.

[baloghadamsoftware]

Issues fixed.

[baloghadamsoftware]

Debug line removed.

[baloghadamsoftware]

lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp

452 ↗

(On Diff #63207)

I made a quick measurement on our build server using clang as target code. Real/user/system times were 75/575/18 for minimal and 76/587/18 for regular. This does not seem too much. However, since the semantics of a copy assignment operator is often composed of the semantics of a destructor and the semantics of a copy constructor implementations often put these two functionalities into separate functions and call them from the destructor, copy constructor and copy assignment operator. Such implementations requires regular inlining to be checked.

[baloghadamsoftware]

I added tests for move assignment operators, but I could not find out any other simple test case than memory leak. However memory leaks are currently only detected by Unix.malloc for malloc. So I tried to replace strdup with malloc, strlen and strcpy, but even in this case leak bug is only reported for string used but not for string unused. That would require a more complex leak checker which we currently do not have.

[dcoughlin]

Other than adding expected notes for the path notes to the test, this looks good to me. Thanks Ádám!

lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1698 ↗

(On Diff #63207)

This is great.

lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp

452 ↗

(On Diff #63207)

Ok, makes sense to me.

test/Analysis/self-assign.cpp

1 ↗

(On Diff #63207)

I think it would be good to add -analyzer-output=text to this test line and check the expected output of that path notes.

[baloghadamsoftware]

Test updated.

[dcoughlin]

Re-opening. Reverted in r275880. It was causing a failure on the bots: http://bb.pgr.jp/builders/cmake-clang-x86_64-linux/builds/51780

[baloghadamsoftware]

Do I use a non-portable way to concatenate strings? "Assuming rhs == *this" becomes "0*this" for some strange reason. I tested it again with the latest master branch and all tests are passing like earlier.

[dcoughlin]

Here is the failing test output in case the bot log goes away:

• TEST 'Clang :: Analysis/self-assign.cpp' FAILED ****

Script:

/home/bb/cmake-clang-x86_64-linux/build/./bin/clang -cc1 -internal-isystem /home/bb/cmake-clang-x86_64-linux/build/bin/../lib/clang/3.9.0/include -nostdsysteminc -std=c++11 -analyze -analyzer-checker=core,cplusplus,unix.Malloc,debug.ExprInspection /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp -verify -analyzer-output=text

Exit Code: 1

Command Output (stderr):

error: 'note' diagnostics expected but not seen:

File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 31: Assuming rhs == *this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 31: Assuming rhs == *this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 31: Assuming rhs != *this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 38: Assuming rhs == *this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 38: Assuming rhs != *this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 65: Assuming rhs == *this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 65: Assuming rhs == *this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 65: Assuming rhs != *this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 72: Assuming rhs == *this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 72: Assuming rhs != *this

error: 'note' diagnostics seen but not expected:

File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 31: 0*this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 31: 0*this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 31: 0*this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 38: 0*this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 38: 0*this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 65: 0*this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 65: 0*this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 65: 0*this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 72: 0*this
File /home/bb/cmake-clang-x86_64-linux/llvm-project/clang/test/Analysis/self-assign.cpp Line 72: 0*this

20 errors generated.

[baloghadamsoftware]

Thx, I checked the output, but I do not understand why a simple string concatenation fails in your test environment. It works on our build server (Linux) with the latest master trunk.

[xazax.hun]

cfe/trunk/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

1738

getName will return a StringRef here. Contatenating const char * and StringRef will give you a Twine. So Msg will be a twine which refers to temporary objects. This will result in a use after free. You shoud convert the result of the concatenation (the Twine) to a std::string, to copy the data and avoid use after free.

[baloghadamsoftware]

Bug path string fixed.

cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td

 def NewDeleteChecker : Checker<"NewDelete">,
   HelpText<"Check for double-free and use-after-free problems. Traces memory managed by new/delete.">,
   DescFile<"MallocChecker.cpp">;
 
 def NewDeleteLeaksChecker : Checker<"NewDeleteLeaks">,
   HelpText<"Check for memory leaks. Traces memory managed by new/delete.">,
   DescFile<"MallocChecker.cpp">;
 
+def CXXSelfAssignmentChecker : Checker<"SelfAssignment">,
+  HelpText<"Checks C++ copy and move assignment operators for self assignment">,
+  DescFile<"CXXSelfAssignmentChecker.cpp">;
+
 } // end: "cplusplus"
 
 let ParentPackage = CplusplusAlpha in {
 
 def VirtualCallChecker : Checker<"VirtualCall">,
   HelpText<"Check virtual function calls during construction or destruction">,
   DescFile<"VirtualCallChecker.cpp">;
 

cfe/trunk/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitor.h

public:
   static const char *getTag();
 
   PathDiagnosticPiece *VisitNode(const ExplodedNode *Succ,
                                  const ExplodedNode *Pred,
                                  BugReporterContext &BRC,
                                  BugReport &BR) override;
 };
 
+class CXXSelfAssignmentBRVisitor final
+  : public BugReporterVisitorImpl<CXXSelfAssignmentBRVisitor> {
+  
+  bool Satisfied;
+
+public:
+  CXXSelfAssignmentBRVisitor() : Satisfied(false) {}
+
+  void Profile(llvm::FoldingSetNodeID &ID) const override {}
+
+  PathDiagnosticPiece *VisitNode(const ExplodedNode *Succ,
+                                 const ExplodedNode *Pred,
+                                 BugReporterContext &BRC,
+                                 BugReport &BR) override;
+};
+
 namespace bugreporter {
 
 /// Attempts to add visitors to trace a null or undefined value back to its
 /// point of origin, whether it is a symbol constrained to null or an explicit
 /// assignment.
 ///
 /// \param N A node "downstream" from the evaluation of the statement.
 /// \param S The statement whose value is null or undefined.

cfe/trunk/lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   CastToStructChecker.cpp
   CheckObjCDealloc.cpp
   CheckObjCInstMethSignature.cpp
   CheckSecuritySyntaxOnly.cpp
   CheckSizeofPointer.cpp
   CheckerDocumentation.cpp
   ChrootChecker.cpp
   ClangCheckers.cpp
+  CXXSelfAssignmentChecker.cpp
   DeadStoresChecker.cpp
   DebugCheckers.cpp
   DereferenceChecker.cpp
   DirectIvarAssignment.cpp
   DivZeroChecker.cpp
   DynamicTypePropagation.cpp
   DynamicTypeChecker.cpp
   ExprInspectionChecker.cpp

cfe/trunk/lib/StaticAnalyzer/Checkers/CXXSelfAssignmentChecker.cpp

+//=== CXXSelfAssignmentChecker.cpp -----------------------------*- C++ -*--===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines CXXSelfAssignmentChecker, which tests all custom defined
+// copy and move assignment operators for the case of self assignment, thus
+// where the parameter refers to the same location where the this pointer
+// points to. The checker itself does not do any checks at all, but it
+// causes the analyzer to check every copy and move assignment operator twice:
+// once for when 'this' aliases with the parameter and once for when it may not.
+// It is the task of the other enabled checkers to find the bugs in these two
+// different cases.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+class CXXSelfAssignmentChecker : public Checker<check::BeginFunction> {
+public:
+  CXXSelfAssignmentChecker();
+  void checkBeginFunction(CheckerContext &C) const;
+};
+}
+
+CXXSelfAssignmentChecker::CXXSelfAssignmentChecker() {}
+
+void CXXSelfAssignmentChecker::checkBeginFunction(CheckerContext &C) const {
+  if (!C.inTopFrame())
+    return;
+  const auto *LCtx = C.getLocationContext();
+  const auto *MD = dyn_cast<CXXMethodDecl>(LCtx->getDecl());
+  if (!MD)
+    return;
+  if (!MD->isCopyAssignmentOperator() && !MD->isMoveAssignmentOperator())
+    return;
+  auto &State = C.getState();
+  auto &SVB = C.getSValBuilder();
+  auto ThisVal =
+      State->getSVal(SVB.getCXXThis(MD, LCtx->getCurrentStackFrame()));
+  auto Param = SVB.makeLoc(State->getRegion(MD->getParamDecl(0), LCtx));
+  auto ParamVal = State->getSVal(Param);
+  ProgramStateRef SelfAssignState = State->bindLoc(Param, ThisVal);
+  C.addTransition(SelfAssignState);
+  ProgramStateRef NonSelfAssignState = State->bindLoc(Param, ParamVal);
+  C.addTransition(NonSelfAssignState);
+}
+
+void ento::registerCXXSelfAssignmentChecker(CheckerManager &Mgr) {
+  Mgr.registerChecker<CXXSelfAssignmentChecker>();
+}

cfe/trunk/lib/StaticAnalyzer/Core/BugReporter.cpp

while (TrimG.popNextReportGraph(ErrorGraph)) {
     // Start building the path diagnostic...
     PathDiagnosticBuilder PDB(*this, R, ErrorGraph.BackMap, &PC);
     const ExplodedNode *N = ErrorGraph.ErrorNode;
 
     // Register additional node visitors.
     R->addVisitor(llvm::make_unique<NilReceiverBRVisitor>());
     R->addVisitor(llvm::make_unique<ConditionBRVisitor>());
     R->addVisitor(llvm::make_unique<LikelyFalsePositiveSuppressionBRVisitor>());
+    R->addVisitor(llvm::make_unique<CXXSelfAssignmentBRVisitor>());
 
     BugReport::VisitorList visitors;
     unsigned origReportConfigToken, finalReportConfigToken;
     LocationContextMap LCM;
 
     // While generating diagnostics, it's possible the visitors will decide
     // new symbols and regions are interesting, or add other visitors based on
     // the information they find. If they do, we need to regenerate the path

cfe/trunk/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

for (ArrayRef<ParmVarDecl*>::iterator I = parms.begin(), E = parms.end();
     SVal BoundVal = State->getSVal(R);
     if (BoundVal.isUndef() || BoundVal.isZeroConstant()) {
       BR.markInteresting(CEnter->getCalleeContext());
       return nullptr;
     }
   }
   return nullptr;
 }
+
+PathDiagnosticPiece *
+CXXSelfAssignmentBRVisitor::VisitNode(const ExplodedNode *Succ,
+                                      const ExplodedNode *Pred,
+                                      BugReporterContext &BRC, BugReport &BR) {
+  if (Satisfied)
+    return nullptr;
+
+  auto Edge = Succ->getLocation().getAs<BlockEdge>();
+  if (!Edge.hasValue())
+    return nullptr;
+
+  auto Tag = Edge->getTag();
+  if (!Tag)
+    return nullptr;
+
+  if (Tag->getTagDescription() != "cplusplus.SelfAssignment")
+    return nullptr;
+
+  Satisfied = true;
+
+  const auto *Met =
+      dyn_cast<CXXMethodDecl>(Succ->getCodeDecl().getAsFunction());
+  assert(Met && "Not a C++ method.");
+  assert((Met->isCopyAssignmentOperator() || Met->isMoveAssignmentOperator()) &&
+         "Not a copy/move assignment operator.");
+
+  const auto *LCtx = Edge->getLocationContext();
+
+  const auto &State = Succ->getState();
+  auto &SVB = State->getStateManager().getSValBuilder();
+
+  const auto Param =
+      State->getSVal(State->getRegion(Met->getParamDecl(0), LCtx));
+  const auto This =
+      State->getSVal(SVB.getCXXThis(Met, LCtx->getCurrentStackFrame()));
+
+  auto L = PathDiagnosticLocation::create(Met, BRC.getSourceManager());
+
+  if (!L.isValid() || !L.asLocation().isValid())
+    return nullptr;
+
+  SmallString<256> Buf;
+  llvm::raw_svector_ostream Out(Buf);
+
+  Out << "Assuming " << Met->getParamDecl(0)->getName() <<
+    ((Param == This) ? " == " : " != ") << "*this";
+
+  auto *Piece = new PathDiagnosticEventPiece(L, Out.str());
+  Piece->addRange(Met->getSourceRange());
+
+  return Piece;
+}

cfe/trunk/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp

static bool shouldSkipFunction(const Decl *D,
   // - The 'init' methods should be reanalyzed because
   //   ObjCNonNilReturnValueChecker assumes that '[super init]' never returns
   //   'nil' and unless we analyze the 'init' functions as top level, we will
   //   not catch errors within defensive code.
   // - We want to reanalyze all ObjC methods as top level to report Retain
   //   Count naming convention errors more aggressively.
   if (isa<ObjCMethodDecl>(D))
     return false;
+  // We also want to reanalyze all C++ copy and move assignment operators to
+  // separately check the two cases where 'this' aliases with the parameter and
+  // where it may not. (cplusplus.SelfAssignmentChecker)
+  if (const auto *MD = dyn_cast<CXXMethodDecl>(D)) {
+    if (MD->isCopyAssignmentOperator() || MD->isMoveAssignmentOperator())
+      return false;
+  }
 
   // Otherwise, if we visited the function before, do not reanalyze it.
   return Visited.count(D);
 }
 
 ExprEngine::InliningModes
 AnalysisConsumer::getInliningModeForFunction(const Decl *D,
                                              const SetOfConstDecls &Visited) {
   // We want to reanalyze all ObjC methods as top level to report Retain
   // Count naming convention errors more aggressively. But we should tune down
   // inlining when reanalyzing an already inlined function.
-  if (Visited.count(D)) {
-    assert(isa<ObjCMethodDecl>(D) &&
-           "We are only reanalyzing ObjCMethods.");
+  if (Visited.count(D) && isa<ObjCMethodDecl>(D)) {
     const ObjCMethodDecl *ObjCM = cast<ObjCMethodDecl>(D);
     if (ObjCM->getMethodFamily() != OMF_init)
       return ExprEngine::Inline_Minimal;
   }
 
   return ExprEngine::Inline_Regular;
 }
 

cfe/trunk/test/Analysis/self-assign.cpp

+// RUN: %clang_cc1 -std=c++11 -analyze -analyzer-checker=core,cplusplus,unix.Malloc,debug.ExprInspection %s -verify -analyzer-output=text
+
+extern "C" char *strdup(const char* s);
+extern "C" void free(void* ptr);
+
+namespace std {
+template<class T> struct remove_reference      { typedef T type; };
+template<class T> struct remove_reference<T&>  { typedef T type; };
+template<class T> struct remove_reference<T&&> { typedef T type; };
+template<class T> typename remove_reference<T>::type&& move(T&& t);
+}
+
+void clang_analyzer_eval(int);
+
+class StringUsed {
+public:
+  StringUsed(const char *s = "") : str(strdup(s)) {}
+  StringUsed(const StringUsed &rhs) : str(strdup(rhs.str)) {}
+  ~StringUsed();
+  StringUsed& operator=(const StringUsed &rhs);
+  StringUsed& operator=(StringUsed &&rhs);
+  operator const char*() const;
+private:
+  char *str;
+};
+
+StringUsed::~StringUsed() {
+  free(str);
+}
+
+StringUsed& StringUsed::operator=(const StringUsed &rhs) { // expected-note{{Assuming rhs == *this}} expected-note{{Assuming rhs == *this}} expected-note{{Assuming rhs != *this}}
+  clang_analyzer_eval(*this == rhs); // expected-warning{{TRUE}} expected-warning{{UNKNOWN}} expected-note{{TRUE}} expected-note{{UNKNOWN}}
+  free(str); // expected-note{{Memory is released}}
+  str = strdup(rhs.str); // expected-warning{{Use of memory after it is freed}}  expected-note{{Use of memory after it is freed}}
+  return *this;
+}
+
+StringUsed& StringUsed::operator=(StringUsed &&rhs) { // expected-note{{Assuming rhs == *this}} expected-note{{Assuming rhs != *this}}
+  clang_analyzer_eval(*this == rhs); // expected-warning{{TRUE}} expected-warning{{UNKNOWN}} expected-note{{TRUE}} expected-note{{UNKNOWN}}
+  str = rhs.str;
+  rhs.str = nullptr; // FIXME: An improved leak checker should warn here
+  return *this;
+}
+
+StringUsed::operator const char*() const {
+  return str;
+}
+
+class StringUnused {
+public:
+  StringUnused(const char *s = "") : str(strdup(s)) {}
+  StringUnused(const StringUnused &rhs) : str(strdup(rhs.str)) {}
+  ~StringUnused();
+  StringUnused& operator=(const StringUnused &rhs);
+  StringUnused& operator=(StringUnused &&rhs);
+  operator const char*() const;
+private:
+  char *str;
+};
+
+StringUnused::~StringUnused() {
+  free(str);
+}
+
+StringUnused& StringUnused::operator=(const StringUnused &rhs) { // expected-note{{Assuming rhs == *this}} expected-note{{Assuming rhs == *this}} expected-note{{Assuming rhs != *this}}
+  clang_analyzer_eval(*this == rhs); // expected-warning{{TRUE}} expected-warning{{UNKNOWN}} expected-note{{TRUE}} expected-note{{UNKNOWN}}
+  free(str); // expected-note{{Memory is released}}
+  str = strdup(rhs.str); // expected-warning{{Use of memory after it is freed}}  expected-note{{Use of memory after it is freed}}
+  return *this;
+}
+
+StringUnused& StringUnused::operator=(StringUnused &&rhs) { // expected-note{{Assuming rhs == *this}} expected-note{{Assuming rhs != *this}}
+  clang_analyzer_eval(*this == rhs); // expected-warning{{TRUE}} expected-warning{{UNKNOWN}} expected-note{{TRUE}} expected-note{{UNKNOWN}}
+  str = rhs.str;
+  rhs.str = nullptr; // FIXME: An improved leak checker should warn here
+  return *this;
+}
+
+StringUnused::operator const char*() const {
+  return str;
+}
+
+
+int main() {
+  StringUsed s1 ("test"), s2;
+  s2 = s1;
+  s2 = std::move(s1);
+  return 0;
+}