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 28namespace clang { 29namespace 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. 39template <typename Key, typename ElementLattice> class MapLattice { 40 using Container = llvm::DenseMap<Key, ElementLattice>; 41 Container C; 42 43public: 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. 111template <typename ElementLattice> 112using VarMapLattice = MapLattice<const clang::VarDecl *, ElementLattice>; 113 114template <typename Key, typename ElementLattice> 115std::ostream & 116operator<<(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 127template <typename ElementLattice> 128std::ostream & 129operator<<(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