Analysis/FlowSensitive/CachedConstAccessorsLattice.h

0001 //===-- CachedConstAccessorsLattice.h ---------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file defines the lattice mixin that additionally maintains a cache of
0010 // stable method call return values to model const accessor member functions.
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CACHED_CONST_ACCESSORS_LATTICE_H
0014 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CACHED_CONST_ACCESSORS_LATTICE_H
0015
0016 #include "clang/AST/Decl.h"
0017 #include "clang/AST/Expr.h"
0018 #include "clang/AST/Type.h"
0019 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
0020 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
0021 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
0022 #include "clang/Analysis/FlowSensitive/Value.h"
0023 #include "llvm/ADT/DenseMap.h"
0024 #include "llvm/ADT/STLFunctionalExtras.h"
0025
0026 namespace clang {
0027 namespace dataflow {
0028
0029 /// A mixin for a lattice that additionally maintains a cache of stable method
0030 /// call return values to model const accessors methods. When a non-const method
0031 /// is called, the cache should be cleared causing the next call to a const
0032 /// method to be considered a different value. NOTE: The user is responsible for
0033 /// clearing the cache.
0034 ///
0035 /// For example:
0036 ///
0037 /// class Bar {
0038 /// public:
0039 ///   const std::optional<Foo>& getFoo() const;
0040 ///   void clear();
0041 /// };
0042 //
0043 /// void func(Bar& s) {
0044 ///   if (s.getFoo().has_value()) {
0045 ///     use(s.getFoo().value()); // safe (checked earlier getFoo())
0046 ///     s.clear();
0047 ///     use(s.getFoo().value()); // unsafe (invalidate cache for s)
0048 ///   }
0049 /// }
0050 template <typename Base> class CachedConstAccessorsLattice : public Base {
0051 public:
0052   using Base::Base; // inherit all constructors
0053
0054   /// Creates or returns a previously created `Value` associated with a const
0055   /// method call `obj.getFoo()` where `RecordLoc` is the
0056   /// `RecordStorageLocation` of `obj`.
0057   /// Returns nullptr if unable to find or create a value.
0058   ///
0059   /// Requirements:
0060   ///
0061   ///  - `CE` should return a value (not a reference or record type)
0062   Value *
0063   getOrCreateConstMethodReturnValue(const RecordStorageLocation &RecordLoc,
0064                                     const CallExpr *CE, Environment &Env);
0065
0066   /// Creates or returns a previously created `StorageLocation` associated with
0067   /// a const method call `obj.getFoo()` where `RecordLoc` is the
0068   /// `RecordStorageLocation` of `obj`.
0069   ///
0070   /// The callback `Initialize` runs on the storage location if newly created.
0071   /// Returns nullptr if unable to find or create a value.
0072   ///
0073   /// Requirements:
0074   ///
0075   ///  - `CE` should return a location (GLValue or a record type).
0076   ///
0077   /// DEPRECATED: switch users to the below overload which takes Callee and Type
0078   /// directly.
0079   StorageLocation *getOrCreateConstMethodReturnStorageLocation(
0080       const RecordStorageLocation &RecordLoc, const CallExpr *CE,
0081       Environment &Env, llvm::function_ref<void(StorageLocation &)> Initialize);
0082
0083   /// Creates or returns a previously created `StorageLocation` associated with
0084   /// a const method call `obj.getFoo()` where `RecordLoc` is the
0085   /// `RecordStorageLocation` of `obj`, `Callee` is the decl for `getFoo`.
0086   ///
0087   /// The callback `Initialize` runs on the storage location if newly created.
0088   ///
0089   /// Requirements:
0090   ///
0091   ///  - `Callee` should return a location (return type is a reference type or a
0092   ///     record type).
0093   StorageLocation &getOrCreateConstMethodReturnStorageLocation(
0094       const RecordStorageLocation &RecordLoc, const FunctionDecl *Callee,
0095       Environment &Env, llvm::function_ref<void(StorageLocation &)> Initialize);
0096
0097   void clearConstMethodReturnValues(const RecordStorageLocation &RecordLoc) {
0098     ConstMethodReturnValues.erase(&RecordLoc);
0099   }
0100
0101   void clearConstMethodReturnStorageLocations(
0102       const RecordStorageLocation &RecordLoc) {
0103     ConstMethodReturnStorageLocations.erase(&RecordLoc);
0104   }
0105
0106   bool operator==(const CachedConstAccessorsLattice &Other) const {
0107     return Base::operator==(Other);
0108   }
0109
0110   LatticeJoinEffect join(const CachedConstAccessorsLattice &Other);
0111
0112 private:
0113   // Maps a record storage location and const method to the value to return
0114   // from that const method.
0115   using ConstMethodReturnValuesType =
0116       llvm::SmallDenseMap<const RecordStorageLocation *,
0117                           llvm::SmallDenseMap<const FunctionDecl *, Value *>>;
0118   ConstMethodReturnValuesType ConstMethodReturnValues;
0119
0120   // Maps a record storage location and const method to the record storage
0121   // location to return from that const method.
0122   using ConstMethodReturnStorageLocationsType = llvm::SmallDenseMap<
0123       const RecordStorageLocation *,
0124       llvm::SmallDenseMap<const FunctionDecl *, StorageLocation *>>;
0125   ConstMethodReturnStorageLocationsType ConstMethodReturnStorageLocations;
0126 };
0127
0128 namespace internal {
0129
0130 template <typename T>
0131 llvm::SmallDenseMap<const RecordStorageLocation *,
0132                     llvm::SmallDenseMap<const FunctionDecl *, T *>>
0133 joinConstMethodMap(
0134     const llvm::SmallDenseMap<const RecordStorageLocation *,
0135                               llvm::SmallDenseMap<const FunctionDecl *, T *>>
0136         &Map1,
0137     const llvm::SmallDenseMap<const RecordStorageLocation *,
0138                               llvm::SmallDenseMap<const FunctionDecl *, T *>>
0139         &Map2,
0140     LatticeEffect &Effect) {
0141   llvm::SmallDenseMap<const RecordStorageLocation *,
0142                       llvm::SmallDenseMap<const FunctionDecl *, T *>>
0143       Result;
0144   for (auto &[Loc, DeclToT] : Map1) {
0145     auto It = Map2.find(Loc);
0146     if (It == Map2.end()) {
0147       Effect = LatticeJoinEffect::Changed;
0148       continue;
0149     }
0150     const auto &OtherDeclToT = It->second;
0151     auto &JoinedDeclToT = Result[Loc];
0152     for (auto [Func, Var] : DeclToT) {
0153       T *OtherVar = OtherDeclToT.lookup(Func);
0154       if (OtherVar == nullptr || OtherVar != Var) {
0155         Effect = LatticeJoinEffect::Changed;
0156         continue;
0157       }
0158       JoinedDeclToT.insert({Func, Var});
0159     }
0160   }
0161   return Result;
0162 }
0163
0164 } // namespace internal
0165
0166 template <typename Base>
0167 LatticeEffect CachedConstAccessorsLattice<Base>::join(
0168     const CachedConstAccessorsLattice<Base> &Other) {
0169
0170   LatticeEffect Effect = Base::join(Other);
0171
0172   // For simplicity, we only retain values that are identical, but not ones that
0173   // are non-identical but equivalent. This is likely to be sufficient in
0174   // practice, and it reduces implementation complexity considerably.
0175
0176   ConstMethodReturnValues =
0177       clang::dataflow::internal::joinConstMethodMap<dataflow::Value>(
0178           ConstMethodReturnValues, Other.ConstMethodReturnValues, Effect);
0179
0180   ConstMethodReturnStorageLocations =
0181       clang::dataflow::internal::joinConstMethodMap<dataflow::StorageLocation>(
0182           ConstMethodReturnStorageLocations,
0183           Other.ConstMethodReturnStorageLocations, Effect);
0184
0185   return Effect;
0186 }
0187
0188 template <typename Base>
0189 Value *CachedConstAccessorsLattice<Base>::getOrCreateConstMethodReturnValue(
0190     const RecordStorageLocation &RecordLoc, const CallExpr *CE,
0191     Environment &Env) {
0192   QualType Type = CE->getType();
0193   assert(!Type.isNull());
0194   assert(!Type->isReferenceType());
0195   assert(!Type->isRecordType());
0196
0197   auto &ObjMap = ConstMethodReturnValues[&RecordLoc];
0198   const FunctionDecl *DirectCallee = CE->getDirectCallee();
0199   if (DirectCallee == nullptr)
0200     return nullptr;
0201   auto it = ObjMap.find(DirectCallee);
0202   if (it != ObjMap.end())
0203     return it->second;
0204
0205   Value *Val = Env.createValue(Type);
0206   if (Val != nullptr)
0207     ObjMap.insert({DirectCallee, Val});
0208   return Val;
0209 }
0210
0211 template <typename Base>
0212 StorageLocation *
0213 CachedConstAccessorsLattice<Base>::getOrCreateConstMethodReturnStorageLocation(
0214     const RecordStorageLocation &RecordLoc, const CallExpr *CE,
0215     Environment &Env, llvm::function_ref<void(StorageLocation &)> Initialize) {
0216   assert(!CE->getType().isNull());
0217   assert(CE->isGLValue() || CE->getType()->isRecordType());
0218   auto &ObjMap = ConstMethodReturnStorageLocations[&RecordLoc];
0219   const FunctionDecl *DirectCallee = CE->getDirectCallee();
0220   if (DirectCallee == nullptr)
0221     return nullptr;
0222   auto it = ObjMap.find(DirectCallee);
0223   if (it != ObjMap.end())
0224     return it->second;
0225
0226   StorageLocation &Loc =
0227       Env.createStorageLocation(CE->getType().getNonReferenceType());
0228   Initialize(Loc);
0229
0230   ObjMap.insert({DirectCallee, &Loc});
0231   return &Loc;
0232 }
0233
0234 template <typename Base>
0235 StorageLocation &
0236 CachedConstAccessorsLattice<Base>::getOrCreateConstMethodReturnStorageLocation(
0237     const RecordStorageLocation &RecordLoc, const FunctionDecl *Callee,
0238     Environment &Env, llvm::function_ref<void(StorageLocation &)> Initialize) {
0239   assert(Callee != nullptr);
0240   QualType Type = Callee->getReturnType();
0241   assert(!Type.isNull());
0242   assert(Type->isReferenceType() || Type->isRecordType());
0243   auto &ObjMap = ConstMethodReturnStorageLocations[&RecordLoc];
0244   auto it = ObjMap.find(Callee);
0245   if (it != ObjMap.end())
0246     return *it->second;
0247
0248   StorageLocation &Loc = Env.createStorageLocation(Type.getNonReferenceType());
0249   Initialize(Loc);
0250
0251   ObjMap.insert({Callee, &Loc});
0252   return Loc;
0253 }
0254
0255 } // namespace dataflow
0256 } // namespace clang
0257
0258 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CACHED_CONST_ACCESSORS_LATTICE_H