clang  15.0.0git
MapLattice.h
Go to the documentation of this file.
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"
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  void insert(const std::pair<const key_type, mapped_type> &P) { C.insert(P); }
58 
59  void insert(std::pair<const key_type, mapped_type> &&P) {
60  C.insert(std::move(P));
61  }
62 
63  unsigned size() const { return C.size(); }
64  bool empty() const { return C.empty(); }
65 
66  iterator begin() { return C.begin(); }
67  iterator end() { return C.end(); }
68  const_iterator begin() const { return C.begin(); }
69  const_iterator end() const { return C.end(); }
70 
71  // Equality is direct equality of underlying map entries. One implication of
72  // this definition is that a map with (only) keys that map to bottom is not
73  // equal to the empty map.
74  friend bool operator==(const MapLattice &LHS, const MapLattice &RHS) {
75  return LHS.C == RHS.C;
76  }
77 
78  friend bool operator!=(const MapLattice &LHS, const MapLattice &RHS) {
79  return !(LHS == RHS);
80  }
81 
82  bool contains(const key_type &K) const { return C.find(K) != C.end(); }
83 
84  iterator find(const key_type &K) { return C.find(K); }
85  const_iterator find(const key_type &K) const { return C.find(K); }
86 
87  mapped_type &operator[](const key_type &K) { return C[K]; }
88 
89  /// If an entry exists in one map but not the other, the missing entry is
90  /// treated as implicitly mapping to `bottom`. So, the joined map contains the
91  /// entry as it was in the source map.
94  for (const auto &O : Other.C) {
95  auto It = C.find(O.first);
96  if (It == C.end()) {
97  C.insert(O);
99  } else if (It->second.join(O.second) == LatticeJoinEffect::Changed)
101  }
102  return Effect;
103  }
104 };
105 
106 /// Convenience alias that captures the common use of map lattices to model
107 /// in-scope variables.
108 template <typename ElementLattice>
110 
111 template <typename Key, typename ElementLattice>
112 std::ostream &
113 operator<<(std::ostream &Os,
115  std::string Separator;
116  Os << "{";
117  for (const auto &E : M) {
118  Os << std::exchange(Separator, ", ") << E.first << " => " << E.second;
119  }
120  Os << "}";
121  return Os;
122 }
123 
124 template <typename ElementLattice>
125 std::ostream &
126 operator<<(std::ostream &Os,
128  std::string Separator;
129  Os << "{";
130  for (const auto &E : M) {
131  Os << std::exchange(Separator, ", ") << E.first->getName().str() << " => "
132  << E.second;
133  }
134  Os << "}";
135  return Os;
136 }
137 } // namespace dataflow
138 } // namespace clang
139 
140 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H
clang::dataflow::MapLattice::begin
iterator begin()
Definition: MapLattice.h:66
clang::dataflow::MapLattice::value_type
typename Container::value_type value_type
Definition: MapLattice.h:46
clang::dataflow::MapLattice::key_type
Key key_type
Definition: MapLattice.h:44
string
string(SUBSTRING ${CMAKE_CURRENT_BINARY_DIR} 0 ${PATH_LIB_START} PATH_HEAD) string(SUBSTRING $
Definition: CMakeLists.txt:22
clang::dataflow::MapLattice::end
const_iterator end() const
Definition: MapLattice.h:69
clang::dataflow::MapLattice::insert
void insert(const std::pair< const key_type, mapped_type > &P)
Definition: MapLattice.h:57
clang::dataflow::MapLattice::end
iterator end()
Definition: MapLattice.h:67
clang::dataflow::operator<<
std::ostream & operator<<(std::ostream &Os, const clang::dataflow::MapLattice< Key, ElementLattice > &M)
Definition: MapLattice.h:113
clang::dataflow::MapLattice::begin
const_iterator begin() const
Definition: MapLattice.h:68
clang::dataflow::MapLattice::contains
bool contains(const key_type &K) const
Definition: MapLattice.h:82
clang::dataflow::LatticeJoinEffect
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
Definition: DataflowLattice.h:21
clang::dataflow::MapLattice::iterator
typename Container::iterator iterator
Definition: MapLattice.h:47
Decl.h
clang::dataflow::MapLattice::join
LatticeJoinEffect join(const MapLattice &Other)
If an entry exists in one map but not the other, the missing entry is treated as implicitly mapping t...
Definition: MapLattice.h:92
clang::dataflow::MapLattice::bottom
static MapLattice bottom()
Definition: MapLattice.h:55
clang::dataflow::LatticeJoinEffect::Changed
@ Changed
clang::dataflow::MapLattice::empty
bool empty() const
Definition: MapLattice.h:64
clang::dataflow::MapLattice::size
unsigned size() const
Definition: MapLattice.h:63
clang::dataflow::MapLattice::const_iterator
typename Container::const_iterator const_iterator
Definition: MapLattice.h:48
clang::dataflow::MapLattice::mapped_type
ElementLattice mapped_type
Definition: MapLattice.h:45
P
StringRef P
Definition: ASTMatchersInternal.cpp:563
DataflowLattice.h
clang::dataflow::MapLattice::operator==
friend bool operator==(const MapLattice &LHS, const MapLattice &RHS)
Definition: MapLattice.h:74
clang::dataflow::MapLattice::MapLattice
MapLattice(Container C)
Definition: MapLattice.h:52
clang::dataflow::MapLattice::find
iterator find(const key_type &K)
Definition: MapLattice.h:84
clang::dataflow::MapLattice::find
const_iterator find(const key_type &K) const
Definition: MapLattice.h:85
clang
Definition: CalledOnceCheck.h:17
clang::dataflow::MapLattice::MapLattice
MapLattice()=default
clang::dataflow::LatticeJoinEffect::Unchanged
@ Unchanged
clang::dataflow::MapLattice
A lattice that maps keys to individual lattice elements.
Definition: MapLattice.h:39
clang::dataflow::MapLattice::insert
void insert(std::pair< const key_type, mapped_type > &&P)
Definition: MapLattice.h:59
clang::dataflow::MapLattice::operator[]
mapped_type & operator[](const key_type &K)
Definition: MapLattice.h:87
DataflowAnalysis.h
clang::dataflow::MapLattice::operator!=
friend bool operator!=(const MapLattice &LHS, const MapLattice &RHS)
Definition: MapLattice.h:78