Viewing file:  MapLattice.h (4.78 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
//===------------------------ 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 <ostream>
#include <string>
#include <utility>
#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 <typename Key, typename ElementLattice> class MapLattice {
using Container = llvm::DenseMap<Key, ElementLattice>;
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<iterator, bool>
insert(const std::pair<const key_type, mapped_type> &P) {
return C.insert(P);
}
std::pair<iterator, bool> insert(std::pair<const key_type, mapped_type> &&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 <typename ElementLattice>
using VarMapLattice = MapLattice<const clang::VarDecl *, ElementLattice>;
template <typename Key, typename ElementLattice>
std::ostream &
operator<<(std::ostream &Os,
const clang::dataflow::MapLattice<Key, ElementLattice> &M) {
std::string Separator;
Os << "{";
for (const auto &E : M) {
Os << std::exchange(Separator, ", ") << E.first << " => " << E.second;
}
Os << "}";
return Os;
}
template <typename ElementLattice>
std::ostream &
operator<<(std::ostream &Os,
const clang::dataflow::VarMapLattice<ElementLattice> &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
|