1 //===------------------------ MapLattice.h ----------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines a parameterized lattice that maps keys to individual 10 // lattice elements (of the parameter lattice type). A typical usage is lifting 11 // a particular lattice to all variables in a lexical scope. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H 16 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H 17 18 #include <ostream> 19 #include <string> 20 #include <utility> 21 22 #include "DataflowAnalysis.h" 23 #include "clang/AST/Decl.h" 24 #include "clang/Analysis/FlowSensitive/DataflowLattice.h" 25 #include "llvm/ADT/DenseMap.h" 26 #include "llvm/ADT/StringRef.h" 27 28 namespace clang { 29 namespace dataflow { 30 31 /// A lattice that maps keys to individual lattice elements. When instantiated 32 /// with an `ElementLattice` that is a bounded semi-lattice, `MapLattice` is 33 /// itself a bounded semi-lattice, so long as the user limits themselves to a 34 /// finite number of keys. In that case, `top` is (implicitly), the map 35 /// containing all valid keys mapped to `top` of `ElementLattice`. 36 /// 37 /// Requirements on `ElementLattice`: 38 /// * Provides standard declarations of a bounded semi-lattice. 39 template <typename Key, typename ElementLattice> class MapLattice { 40 using Container = llvm::DenseMap<Key, ElementLattice>; 41 Container C; 42 43 public: 44 using key_type = Key; 45 using mapped_type = ElementLattice; 46 using value_type = typename Container::value_type; 47 using iterator = typename Container::iterator; 48 using const_iterator = typename Container::const_iterator; 49 50 MapLattice() = default; 51 52 explicit MapLattice(Container C) { C = std::move(C); } 53 54 // The `bottom` element is the empty map. 55 static MapLattice bottom() { return MapLattice(); } 56 57 std::pair<iterator, bool> 58 insert(const std::pair<const key_type, mapped_type> &P) { 59 return C.insert(P); 60 } 61 62 std::pair<iterator, bool> insert(std::pair<const key_type, mapped_type> &&P) { 63 return C.insert(std::move(P)); 64 } 65 66 unsigned size() const { return C.size(); } 67 bool empty() const { return C.empty(); } 68 69 iterator begin() { return C.begin(); } 70 iterator end() { return C.end(); } 71 const_iterator begin() const { return C.begin(); } 72 const_iterator end() const { return C.end(); } 73 74 // Equality is direct equality of underlying map entries. One implication of 75 // this definition is that a map with (only) keys that map to bottom is not 76 // equal to the empty map. 77 friend bool operator==(const MapLattice &LHS, const MapLattice &RHS) { 78 return LHS.C == RHS.C; 79 } 80 81 friend bool operator!=(const MapLattice &LHS, const MapLattice &RHS) { 82 return !(LHS == RHS); 83 } 84 85 bool contains(const key_type &K) const { return C.find(K) != C.end(); } 86 87 iterator find(const key_type &K) { return C.find(K); } 88 const_iterator find(const key_type &K) const { return C.find(K); } 89 90 mapped_type &operator[](const key_type &K) { return C[K]; } 91 92 /// If an entry exists in one map but not the other, the missing entry is 93 /// treated as implicitly mapping to `bottom`. So, the joined map contains the 94 /// entry as it was in the source map. 95 LatticeJoinEffect join(const MapLattice &Other) { 96 LatticeJoinEffect Effect = LatticeJoinEffect::Unchanged; 97 for (const auto &O : Other.C) { 98 auto It = C.find(O.first); 99 if (It == C.end()) { 100 C.insert(O); 101 Effect = LatticeJoinEffect::Changed; 102 } else if (It->second.join(O.second) == LatticeJoinEffect::Changed) 103 Effect = LatticeJoinEffect::Changed; 104 } 105 return Effect; 106 } 107 }; 108 109 /// Convenience alias that captures the common use of map lattices to model 110 /// in-scope variables. 111 template <typename ElementLattice> 112 using VarMapLattice = MapLattice<const clang::VarDecl *, ElementLattice>; 113 114 template <typename Key, typename ElementLattice> 115 std::ostream & 116 operator<<(std::ostream &Os, 117 const clang::dataflow::MapLattice<Key, ElementLattice> &M) { 118 std::string Separator; 119 Os << "{"; 120 for (const auto &E : M) { 121 Os << std::exchange(Separator, ", ") << E.first << " => " << E.second; 122 } 123 Os << "}"; 124 return Os; 125 } 126 127 template <typename ElementLattice> 128 std::ostream & 129 operator<<(std::ostream &Os, 130 const clang::dataflow::VarMapLattice<ElementLattice> &M) { 131 std::string Separator; 132 Os << "{"; 133 for (const auto &E : M) { 134 Os << std::exchange(Separator, ", ") << E.first->getName().str() << " => " 135 << E.second; 136 } 137 Os << "}"; 138 return Os; 139 } 140 } // namespace dataflow 141 } // namespace clang 142 143 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H 144