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

source code of clang/include/clang/Analysis/FlowSensitive/MapLattice.h