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
25namespace clang {
26namespace 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.
32class StorageLocation {
33public:
34  enum class Kind {
35    Scalar,
36    Record,
37  };
38
39  StorageLocation(Kind LocKind, QualType Type) : LocKind(LocKind), Type(Type) {
40    assert(Type.isNull() || !Type->isReferenceType());
41  }
42
43  // Non-copyable because addresses of storage locations are used as their
44  // identities throughout framework and user code. The framework is responsible
45  // for construction and destruction of storage locations.
46  StorageLocation(const StorageLocation &) = delete;
47  StorageLocation &operator=(const StorageLocation &) = delete;
48
49  virtual ~StorageLocation() = default;
50
51  Kind getKind() const { return LocKind; }
52
53  QualType getType() const { return Type; }
54
55private:
56  Kind LocKind;
57  QualType Type;
58};
59
60/// A storage location that is not subdivided further for the purposes of
61/// abstract interpretation. For example: `int`, `int*`, `int&`.
62class ScalarStorageLocation final : public StorageLocation {
63public:
64  explicit ScalarStorageLocation(QualType Type)
65      : StorageLocation(Kind::Scalar, Type) {}
66
67  static bool classof(const StorageLocation *Loc) {
68    return Loc->getKind() == Kind::Scalar;
69  }
70};
71
72/// A storage location for a record (struct, class, or union).
73///
74/// Contains storage locations for all modeled fields of the record (also
75/// referred to as "children"). The child map is flat, so accessible members of
76/// the base class are directly accessible as children of this location.
77///
78/// Record storage locations may also contain so-called synthetic fields. These
79/// are typically used to model the internal state of a class (e.g. the value
80/// stored in a `std::optional`) without having to depend on that class's
81/// implementation details. All `RecordStorageLocation`s of a given type should
82/// have the same synthetic fields.
83///
84/// The storage location for a field of reference type may be null. This
85/// typically occurs in one of two situations:
86/// - The record has not been fully initialized.
87/// - The maximum depth for modelling a self-referential data structure has been
88///   reached.
89/// Storage locations for fields of all other types must be non-null.
90///
91/// FIXME: Currently, the storage location of unions is modelled the same way as
92/// that of structs or classes. Eventually, we need to change this modelling so
93/// that all of the members of a given union have the same storage location.
94class RecordStorageLocation final : public StorageLocation {
95public:
96  using FieldToLoc = llvm::DenseMap<const ValueDecl *, StorageLocation *>;
97  using SyntheticFieldMap = llvm::StringMap<StorageLocation *>;
98
99  RecordStorageLocation(QualType Type, FieldToLoc TheChildren,
100                        SyntheticFieldMap TheSyntheticFields)
101      : StorageLocation(Kind::Record, Type), Children(std::move(TheChildren)),
102        SyntheticFields(std::move(TheSyntheticFields)) {
103    assert(!Type.isNull());
104    assert(Type->isRecordType());
105    assert([this] {
106      for (auto [Field, Loc] : Children) {
107        if (!Field->getType()->isReferenceType() && Loc == nullptr)
108          return false;
109      }
110      return true;
111    }());
112  }
113
114  static bool classof(const StorageLocation *Loc) {
115    return Loc->getKind() == Kind::Record;
116  }
117
118  /// Returns the child storage location for `D`.
119  ///
120  /// May return null if `D` has reference type; guaranteed to return non-null
121  /// in all other cases.
122  ///
123  /// Note that it is an error to call this with a field that does not exist.
124  /// The function does not return null in this case.
125  StorageLocation *getChild(const ValueDecl &D) const {
126    auto It = Children.find(&D);
127    LLVM_DEBUG({
128      if (It == Children.end()) {
129        llvm::dbgs() << "Couldn't find child " << D.getNameAsString()
130                     << " on StorageLocation " << this << " of type "
131                     << getType() << "\n";
132        llvm::dbgs() << "Existing children:\n";
133        for ([[maybe_unused]] auto [Field, Loc] : Children) {
134          llvm::dbgs() << Field->getNameAsString() << "\n";
135        }
136      }
137    });
138    assert(It != Children.end());
139    return It->second;
140  }
141
142  /// Returns the storage location for the synthetic field `Name`.
143  /// The synthetic field must exist.
144  StorageLocation &getSyntheticField(llvm::StringRef Name) const {
145    StorageLocation *Loc = SyntheticFields.lookup(Name);
146    assert(Loc != nullptr);
147    return *Loc;
148  }
149
150  llvm::iterator_range<SyntheticFieldMap::const_iterator>
151  synthetic_fields() const {
152    return {SyntheticFields.begin(), SyntheticFields.end()};
153  }
154
155  /// Changes the child storage location for a field `D` of reference type.
156  /// All other fields cannot change their storage location and always retain
157  /// the storage location passed to the `RecordStorageLocation` constructor.
158  ///
159  /// Requirements:
160  ///
161  ///  `D` must have reference type.
162  void setChild(const ValueDecl &D, StorageLocation *Loc) {
163    assert(D.getType()->isReferenceType());
164    Children[&D] = Loc;
165  }
166
167  llvm::iterator_range<FieldToLoc::const_iterator> children() const {
168    return {Children.begin(), Children.end()};
169  }
170
171private:
172  FieldToLoc Children;
173  SyntheticFieldMap SyntheticFields;
174};
175
176} // namespace dataflow
177} // namespace clang
178
179#undef DEBUG_TYPE
180
181#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H
182