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(obj&: Separator, new_val: ", " ) << 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(obj&: Separator, new_val: ", " ) << 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 | |