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