clang  16.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  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.
97  for (const auto &O : Other.C) {
98  auto It = C.find(O.first);
99  if (It == C.end()) {
100  C.insert(O);
102  } else if (It->second.join(O.second) == 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>
113 
114 template <typename Key, typename ElementLattice>
115 std::ostream &
116 operator<<(std::ostream &Os,
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,
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
clang::dataflow::MapLattice::begin
iterator begin()
Definition: MapLattice.h:69
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:72
clang::dataflow::MapLattice::insert
std::pair< iterator, bool > insert(std::pair< const key_type, mapped_type > &&P)
Definition: MapLattice.h:62
clang::dataflow::MapLattice::end
iterator end()
Definition: MapLattice.h:70
clang::dataflow::operator<<
std::ostream & operator<<(std::ostream &Os, const clang::dataflow::MapLattice< Key, ElementLattice > &M)
Definition: MapLattice.h:116
clang::dataflow::MapLattice::begin
const_iterator begin() const
Definition: MapLattice.h:71
clang::dataflow::MapLattice::contains
bool contains(const key_type &K) const
Definition: MapLattice.h:85
clang::dataflow::LatticeJoinEffect
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
Definition: DataflowLattice.h:23
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:95
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:67
clang::dataflow::MapLattice::insert
std::pair< iterator, bool > insert(const std::pair< const key_type, mapped_type > &P)
Definition: MapLattice.h:58
clang::dataflow::MapLattice::size
unsigned size() const
Definition: MapLattice.h:66
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:77
clang::dataflow::MapLattice::MapLattice
MapLattice(Container C)
Definition: MapLattice.h:52
clang::dataflow::MapLattice::find
iterator find(const key_type &K)
Definition: MapLattice.h:87
clang::dataflow::MapLattice::find
const_iterator find(const key_type &K) const
Definition: MapLattice.h:88
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::operator[]
mapped_type & operator[](const key_type &K)
Definition: MapLattice.h:90
DataflowAnalysis.h
clang::dataflow::MapLattice::operator!=
friend bool operator!=(const MapLattice &LHS, const MapLattice &RHS)
Definition: MapLattice.h:81