1 //===-- StorageLocation.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 classes that represent elements of the local variable store
10 // and of the heap during dataflow analysis.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H
15 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H
16 
17 #include "clang/AST/Decl.h"
18 #include "clang/AST/Type.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/Support/Debug.h"
21 #include <cassert>
22 
23 #define DEBUG_TYPE "dataflow"
24 
25 namespace clang {
26 namespace dataflow {
27 
28 /// Base class for elements of the local variable store and of the heap.
29 ///
30 /// Each storage location holds a value. The mapping from storage locations to
31 /// values is stored in the environment.
32 class StorageLocation {
33 public:
34   enum class Kind { Scalar, Aggregate };
35 
36   StorageLocation(Kind LocKind, QualType Type) : LocKind(LocKind), Type(Type) {
37     assert(Type.isNull() || !Type->isReferenceType());
38   }
39 
40   // Non-copyable because addresses of storage locations are used as their
41   // identities throughout framework and user code. The framework is responsible
42   // for construction and destruction of storage locations.
43   StorageLocation(const StorageLocation &) = delete;
44   StorageLocation &operator=(const StorageLocation &) = delete;
45 
46   virtual ~StorageLocation() = default;
47 
48   Kind getKind() const { return LocKind; }
49 
50   QualType getType() const { return Type; }
51 
52 private:
53   Kind LocKind;
54   QualType Type;
55 };
56 
57 /// A storage location that is not subdivided further for the purposes of
58 /// abstract interpretation. For example: `int`, `int*`, `int&`.
59 class ScalarStorageLocation final : public StorageLocation {
60 public:
61   explicit ScalarStorageLocation(QualType Type)
62       : StorageLocation(Kind::Scalar, Type) {}
63 
64   static bool classof(const StorageLocation *Loc) {
65     return Loc->getKind() == Kind::Scalar;
66   }
67 };
68 
69 /// A storage location which is subdivided into smaller storage locations that
70 /// can be traced independently by abstract interpretation. For example: a
71 /// struct with public members. The child map is flat, so when used for a struct
72 /// or class type, all accessible members of base struct and class types are
73 /// directly accesible as children of this location.
74 ///
75 /// The storage location for a field of reference type may be null. This
76 /// typically occurs in one of two situations:
77 /// - The record has not been fully initialized.
78 /// - The maximum depth for modelling a self-referential data structure has been
79 ///   reached.
80 /// Storage locations for fields of all other types must be non-null.
81 ///
82 /// FIXME: Currently, the storage location of unions is modelled the same way as
83 /// that of structs or classes. Eventually, we need to change this modelling so
84 /// that all of the members of a given union have the same storage location.
85 class AggregateStorageLocation final : public StorageLocation {
86 public:
87   using FieldToLoc = llvm::DenseMap<const ValueDecl *, StorageLocation *>;
88 
89   explicit AggregateStorageLocation(QualType Type)
90       : AggregateStorageLocation(Type, FieldToLoc()) {}
91 
92   AggregateStorageLocation(QualType Type, FieldToLoc TheChildren)
93       : StorageLocation(Kind::Aggregate, Type),
94         Children(std::move(TheChildren)) {
95     assert(!Type.isNull());
96     assert(Type->isRecordType());
97     assert([this] {
98       for (auto [Field, Loc] : Children) {
99         if (!Field->getType()->isReferenceType() && Loc == nullptr)
100           return false;
101       }
102       return true;
103     }());
104   }
105 
106   static bool classof(const StorageLocation *Loc) {
107     return Loc->getKind() == Kind::Aggregate;
108   }
109 
110   /// Returns the child storage location for `D`.
111   ///
112   /// May return null if `D` has reference type; guaranteed to return non-null
113   /// in all other cases.
114   ///
115   /// Note that it is an error to call this with a field that does not exist.
116   /// The function does not return null in this case.
117   StorageLocation *getChild(const ValueDecl &D) const {
118     auto It = Children.find(&D);
119     LLVM_DEBUG({
120       if (It == Children.end()) {
121         llvm::dbgs() << "Couldn't find child " << D.getNameAsString()
122                      << " on StorageLocation " << this << " of type "
123                      << getType() << "\n";
124         llvm::dbgs() << "Existing children:\n";
125         for ([[maybe_unused]] auto [Field, Loc] : Children) {
126           llvm::dbgs() << Field->getNameAsString() << "\n";
127         }
128       }
129     });
130     assert(It != Children.end());
131     return It->second;
132   }
133 
134   /// Changes the child storage location for a field `D` of reference type.
135   /// All other fields cannot change their storage location and always retain
136   /// the storage location passed to the `AggregateStorageLocation` constructor.
137   ///
138   /// Requirements:
139   ///
140   ///  `D` must have reference type.
141   void setChild(const ValueDecl &D, StorageLocation *Loc) {
142     assert(D.getType()->isReferenceType());
143     Children[&D] = Loc;
144   }
145 
146   llvm::iterator_range<FieldToLoc::const_iterator> children() const {
147     return {Children.begin(), Children.end()};
148   }
149 
150 private:
151   FieldToLoc Children;
152 };
153 
154 } // namespace dataflow
155 } // namespace clang
156 
157 #undef DEBUG_TYPE
158 
159 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H
160