Analysis/FlowSensitive/MapLattice.h

0001 //===------------------------ MapLattice.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 a parameterized lattice that maps keys to individual
0010 //  lattice elements (of the parameter lattice type). A typical usage is lifting
0011 //  a particular lattice to all variables in a lexical scope.
0012 //
0013 //===----------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H
0016 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H
0017
0018 #include <ostream>
0019 #include <string>
0020 #include <utility>
0021
0022 #include "DataflowAnalysis.h"
0023 #include "clang/AST/Decl.h"
0024 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
0025 #include "llvm/ADT/DenseMap.h"
0026 #include "llvm/ADT/StringRef.h"
0027
0028 namespace clang {
0029 namespace dataflow {
0030
0031 /// A lattice that maps keys to individual lattice elements. When instantiated
0032 /// with an `ElementLattice` that is a bounded semi-lattice, `MapLattice` is
0033 /// itself a bounded semi-lattice, so long as the user limits themselves to a
0034 /// finite number of keys. In that case, `top` is (implicitly), the map
0035 /// containing all valid keys mapped to `top` of `ElementLattice`.
0036 ///
0037 /// Requirements on `ElementLattice`:
0038 /// * Provides standard declarations of a bounded semi-lattice.
0039 template <typename Key, typename ElementLattice> class MapLattice {
0040   using Container = llvm::DenseMap<Key, ElementLattice>;
0041   Container C;
0042
0043 public:
0044   using key_type = Key;
0045   using mapped_type = ElementLattice;
0046   using value_type = typename Container::value_type;
0047   using iterator = typename Container::iterator;
0048   using const_iterator = typename Container::const_iterator;
0049
0050   MapLattice() = default;
0051
0052   explicit MapLattice(Container C) : C{std::move(C)} {};
0053
0054   // The `bottom` element is the empty map.
0055   static MapLattice bottom() { return MapLattice(); }
0056
0057   std::pair<iterator, bool>
0058   insert(const std::pair<const key_type, mapped_type> &P) {
0059     return C.insert(P);
0060   }
0061
0062   std::pair<iterator, bool> insert(std::pair<const key_type, mapped_type> &&P) {
0063     return C.insert(std::move(P));
0064   }
0065
0066   unsigned size() const { return C.size(); }
0067   bool empty() const { return C.empty(); }
0068
0069   iterator begin() { return C.begin(); }
0070   iterator end() { return C.end(); }
0071   const_iterator begin() const { return C.begin(); }
0072   const_iterator end() const { return C.end(); }
0073
0074   // Equality is direct equality of underlying map entries. One implication of
0075   // this definition is that a map with (only) keys that map to bottom is not
0076   // equal to the empty map.
0077   friend bool operator==(const MapLattice &LHS, const MapLattice &RHS) {
0078     return LHS.C == RHS.C;
0079   }
0080
0081   friend bool operator!=(const MapLattice &LHS, const MapLattice &RHS) {
0082     return !(LHS == RHS);
0083   }
0084
0085   bool contains(const key_type &K) const { return C.find(K) != C.end(); }
0086
0087   iterator find(const key_type &K) { return C.find(K); }
0088   const_iterator find(const key_type &K) const { return C.find(K); }
0089
0090   mapped_type &operator[](const key_type &K) { return C[K]; }
0091
0092   /// If an entry exists in one map but not the other, the missing entry is
0093   /// treated as implicitly mapping to `bottom`. So, the joined map contains the
0094   /// entry as it was in the source map.
0095   LatticeJoinEffect join(const MapLattice &Other) {
0096     LatticeJoinEffect Effect = LatticeJoinEffect::Unchanged;
0097     for (const auto &O : Other.C) {
0098       auto It = C.find(O.first);
0099       if (It == C.end()) {
0100         C.insert(O);
0101         Effect = LatticeJoinEffect::Changed;
0102       } else if (It->second.join(O.second) == LatticeJoinEffect::Changed)
0103         Effect = LatticeJoinEffect::Changed;
0104     }
0105     return Effect;
0106   }
0107 };
0108
0109 /// Convenience alias that captures the common use of map lattices to model
0110 /// in-scope variables.
0111 template <typename ElementLattice>
0112 using VarMapLattice = MapLattice<const clang::VarDecl *, ElementLattice>;
0113
0114 template <typename Key, typename ElementLattice>
0115 std::ostream &
0116 operator<<(std::ostream &Os,
0117            const clang::dataflow::MapLattice<Key, ElementLattice> &M) {
0118   std::string Separator;
0119   Os << "{";
0120   for (const auto &E : M) {
0121     Os << std::exchange(Separator, ", ") << E.first << " => " << E.second;
0122   }
0123   Os << "}";
0124   return Os;
0125 }
0126
0127 template <typename ElementLattice>
0128 std::ostream &
0129 operator<<(std::ostream &Os,
0130            const clang::dataflow::VarMapLattice<ElementLattice> &M) {
0131   std::string Separator;
0132   Os << "{";
0133   for (const auto &E : M) {
0134     Os << std::exchange(Separator, ", ") << E.first->getName().str() << " => "
0135        << E.second;
0136   }
0137   Os << "}";
0138   return Os;
0139 }
0140 } // namespace dataflow
0141 } // namespace clang
0142
0143 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H