//===------------------------ MapLattice.h ----------------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This file defines a parameterized lattice that maps keys to individual // lattice elements (of the parameter lattice type). A typical usage is lifting // a particular lattice to all variables in a lexical scope. // //===----------------------------------------------------------------------===// #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H #include #include #include #include "DataflowAnalysis.h" #include "clang/AST/Decl.h" #include "clang/Analysis/FlowSensitive/DataflowLattice.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/StringRef.h" namespace clang { namespace dataflow { /// A lattice that maps keys to individual lattice elements. When instantiated /// with an `ElementLattice` that is a bounded semi-lattice, `MapLattice` is /// itself a bounded semi-lattice, so long as the user limits themselves to a /// finite number of keys. In that case, `top` is (implicitly), the map /// containing all valid keys mapped to `top` of `ElementLattice`. /// /// Requirements on `ElementLattice`: /// * Provides standard declarations of a bounded semi-lattice. template class MapLattice { using Container = llvm::DenseMap; Container C; public: using key_type = Key; using mapped_type = ElementLattice; using value_type = typename Container::value_type; using iterator = typename Container::iterator; using const_iterator = typename Container::const_iterator; MapLattice() = default; explicit MapLattice(Container C) { C = std::move(C); } // The `bottom` element is the empty map. static MapLattice bottom() { return MapLattice(); } std::pair insert(const std::pair &P) { return C.insert(P); } std::pair insert(std::pair &&P) { return C.insert(std::move(P)); } unsigned size() const { return C.size(); } bool empty() const { return C.empty(); } iterator begin() { return C.begin(); } iterator end() { return C.end(); } const_iterator begin() const { return C.begin(); } const_iterator end() const { return C.end(); } // Equality is direct equality of underlying map entries. One implication of // this definition is that a map with (only) keys that map to bottom is not // equal to the empty map. friend bool operator==(const MapLattice &LHS, const MapLattice &RHS) { return LHS.C == RHS.C; } friend bool operator!=(const MapLattice &LHS, const MapLattice &RHS) { return !(LHS == RHS); } bool contains(const key_type &K) const { return C.find(K) != C.end(); } iterator find(const key_type &K) { return C.find(K); } const_iterator find(const key_type &K) const { return C.find(K); } mapped_type &operator[](const key_type &K) { return C[K]; } /// If an entry exists in one map but not the other, the missing entry is /// treated as implicitly mapping to `bottom`. So, the joined map contains the /// entry as it was in the source map. LatticeJoinEffect join(const MapLattice &Other) { LatticeJoinEffect Effect = LatticeJoinEffect::Unchanged; for (const auto &O : Other.C) { auto It = C.find(O.first); if (It == C.end()) { C.insert(O); Effect = LatticeJoinEffect::Changed; } else if (It->second.join(O.second) == LatticeJoinEffect::Changed) Effect = LatticeJoinEffect::Changed; } return Effect; } }; /// Convenience alias that captures the common use of map lattices to model /// in-scope variables. template using VarMapLattice = MapLattice; template std::ostream & operator<<(std::ostream &Os, const clang::dataflow::MapLattice &M) { std::string Separator; Os << "{"; for (const auto &E : M) { Os << std::exchange(Separator, ", ") << E.first << " => " << E.second; } Os << "}"; return Os; } template std::ostream & operator<<(std::ostream &Os, const clang::dataflow::VarMapLattice &M) { std::string Separator; Os << "{"; for (const auto &E : M) { Os << std::exchange(Separator, ", ") << E.first->getName().str() << " => " << E.second; } Os << "}"; return Os; } } // namespace dataflow } // namespace clang #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H