Coverage Report

Created: 2022-07-16 07:03

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
Line
Count
Source (jump to first uncovered line)
1
//===-- DataflowEnvironment.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 an Environment class that is used by dataflow analyses
10
//  that run over Control-Flow Graphs (CFGs) to keep track of the state of the
11
//  program at given program points.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
16
#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
17
18
#include "clang/AST/Decl.h"
19
#include "clang/AST/DeclBase.h"
20
#include "clang/AST/Expr.h"
21
#include "clang/AST/Type.h"
22
#include "clang/AST/TypeOrdering.h"
23
#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
24
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
25
#include "clang/Analysis/FlowSensitive/StorageLocation.h"
26
#include "clang/Analysis/FlowSensitive/Value.h"
27
#include "llvm/ADT/DenseMap.h"
28
#include "llvm/ADT/DenseSet.h"
29
#include <memory>
30
#include <type_traits>
31
#include <utility>
32
33
namespace clang {
34
namespace dataflow {
35
36
/// Indicates what kind of indirections should be skipped past when retrieving
37
/// storage locations or values.
38
///
39
/// FIXME: Consider renaming this or replacing it with a more appropriate model.
40
/// See the discussion in https://reviews.llvm.org/D116596 for context.
41
enum class SkipPast {
42
  /// No indirections should be skipped past.
43
  None,
44
  /// An optional reference should be skipped past.
45
  Reference,
46
  /// An optional reference should be skipped past, then an optional pointer
47
  /// should be skipped past.
48
  ReferenceThenPointer,
49
};
50
51
/// Holds the state of the program (store and heap) at a given program point.
52
///
53
/// WARNING: Symbolic values that are created by the environment for static
54
/// local and global variables are not currently invalidated on function calls.
55
/// This is unsound and should be taken into account when designing dataflow
56
/// analyses.
57
class Environment {
58
public:
59
  /// Supplements `Environment` with non-standard comparison and join
60
  /// operations.
61
  class ValueModel {
62
  public:
63
398
    virtual ~ValueModel() = default;
64
65
    /// Returns true if and only if `Val1` is equivalent to `Val2`.
66
    ///
67
    /// Requirements:
68
    ///
69
    ///  `Val1` and `Val2` must be distinct.
70
    ///
71
    ///  `Val1` and `Val2` must model values of type `Type`.
72
    ///
73
    ///  `Val1` and `Val2` must be assigned to the same storage location in
74
    ///  `Env1` and `Env2` respectively.
75
    virtual bool compareEquivalent(QualType Type, const Value &Val1,
76
                                   const Environment &Env1, const Value &Val2,
77
5
                                   const Environment &Env2) {
78
      // FIXME: Consider adding QualType to StructValue and removing the Type
79
      // argument here.
80
      //
81
      // FIXME: default to a sound comparison and/or expand the comparison logic
82
      // built into the framework to support broader forms of equivalence than
83
      // strict pointer equality.
84
5
      return true;
85
5
    }
86
87
    /// Modifies `MergedVal` to approximate both `Val1` and `Val2`. This could
88
    /// be a strict lattice join or a more general widening operation.
89
    ///
90
    /// If this function returns true, `MergedVal` will be assigned to a storage
91
    /// location of type `Type` in `MergedEnv`.
92
    ///
93
    /// `Env1` and `Env2` can be used to query child values and path condition
94
    /// implications of `Val1` and `Val2` respectively.
95
    ///
96
    /// Requirements:
97
    ///
98
    ///  `Val1` and `Val2` must be distinct.
99
    ///
100
    ///  `Val1`, `Val2`, and `MergedVal` must model values of type `Type`.
101
    ///
102
    ///  `Val1` and `Val2` must be assigned to the same storage location in
103
    ///  `Env1` and `Env2` respectively.
104
    virtual bool merge(QualType Type, const Value &Val1,
105
                       const Environment &Env1, const Value &Val2,
106
                       const Environment &Env2, Value &MergedVal,
107
2
                       Environment &MergedEnv) {
108
2
      return true;
109
2
    }
110
  };
111
112
  /// Creates an environment that uses `DACtx` to store objects that encompass
113
  /// the state of a program.
114
  explicit Environment(DataflowAnalysisContext &DACtx);
115
116
  Environment(const Environment &Other);
117
  Environment &operator=(const Environment &Other);
118
119
5.22k
  Environment(Environment &&Other) = default;
120
512
  Environment &operator=(Environment &&Other) = default;
121
122
  /// Creates an environment that uses `DACtx` to store objects that encompass
123
  /// the state of a program.
124
  ///
125
  /// If `DeclCtx` is a function, initializes the environment with symbolic
126
  /// representations of the function parameters.
127
  ///
128
  /// If `DeclCtx` is a non-static member function, initializes the environment
129
  /// with a symbolic representation of the `this` pointee.
130
  Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx);
131
132
  /// Returns true if and only if the environment is equivalent to `Other`, i.e
133
  /// the two environments:
134
  ///  - have the same mappings from declarations to storage locations,
135
  ///  - have the same mappings from expressions to storage locations,
136
  ///  - have the same or equivalent (according to `Model`) values assigned to
137
  ///    the same storage locations.
138
  ///
139
  /// Requirements:
140
  ///
141
  ///  `Other` and `this` must use the same `DataflowAnalysisContext`.
142
  bool equivalentTo(const Environment &Other,
143
                    Environment::ValueModel &Model) const;
144
145
  /// Joins the environment with `Other` by taking the intersection of storage
146
  /// locations and values that are stored in them. Distinct values that are
147
  /// assigned to the same storage locations in the environment and `Other` are
148
  /// merged using `Model`.
149
  ///
150
  /// Requirements:
151
  ///
152
  ///  `Other` and `this` must use the same `DataflowAnalysisContext`.
153
  LatticeJoinEffect join(const Environment &Other,
154
                         Environment::ValueModel &Model);
155
156
  // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`,
157
  // `getStableStorageLocation`, or something more appropriate.
158
159
  /// Creates a storage location appropriate for `Type`. Does not assign a value
160
  /// to the returned storage location in the environment.
161
  ///
162
  /// Requirements:
163
  ///
164
  ///  `Type` must not be null.
165
  StorageLocation &createStorageLocation(QualType Type);
166
167
  /// Creates a storage location for `D`. Does not assign the returned storage
168
  /// location to `D` in the environment. Does not assign a value to the
169
  /// returned storage location in the environment.
170
  StorageLocation &createStorageLocation(const VarDecl &D);
171
172
  /// Creates a storage location for `E`. Does not assign the returned storage
173
  /// location to `E` in the environment. Does not assign a value to the
174
  /// returned storage location in the environment.
175
  StorageLocation &createStorageLocation(const Expr &E);
176
177
  /// Assigns `Loc` as the storage location of `D` in the environment.
178
  ///
179
  /// Requirements:
180
  ///
181
  ///  `D` must not be assigned a storage location in the environment.
182
  void setStorageLocation(const ValueDecl &D, StorageLocation &Loc);
183
184
  /// Returns the storage location assigned to `D` in the environment, applying
185
  /// the `SP` policy for skipping past indirections, or null if `D` isn't
186
  /// assigned a storage location in the environment.
187
  StorageLocation *getStorageLocation(const ValueDecl &D, SkipPast SP) const;
188
189
  /// Assigns `Loc` as the storage location of `E` in the environment.
190
  ///
191
  /// Requirements:
192
  ///
193
  ///  `E` must not be assigned a storage location in the environment.
194
  void setStorageLocation(const Expr &E, StorageLocation &Loc);
195
196
  /// Returns the storage location assigned to `E` in the environment, applying
197
  /// the `SP` policy for skipping past indirections, or null if `E` isn't
198
  /// assigned a storage location in the environment.
199
  StorageLocation *getStorageLocation(const Expr &E, SkipPast SP) const;
200
201
  /// Returns the storage location assigned to the `this` pointee in the
202
  /// environment or null if the `this` pointee has no assigned storage location
203
  /// in the environment.
204
  StorageLocation *getThisPointeeStorageLocation() const;
205
206
  /// Returns a pointer value that represents a null pointer. Calls with
207
  /// `PointeeType` that are canonically equivalent will return the same result.
208
  PointerValue &getOrCreateNullPointerValue(QualType PointeeType);
209
210
  /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
211
  /// return null. If `Type` is a pointer or reference type, creates all the
212
  /// necessary storage locations and values for indirections until it finds a
213
  /// non-pointer/non-reference type.
214
  ///
215
  /// Requirements:
216
  ///
217
  ///  `Type` must not be null.
218
  Value *createValue(QualType Type);
219
220
  /// Assigns `Val` as the value of `Loc` in the environment.
221
  void setValue(const StorageLocation &Loc, Value &Val);
222
223
  /// Returns the value assigned to `Loc` in the environment or null if `Loc`
224
  /// isn't assigned a value in the environment.
225
  Value *getValue(const StorageLocation &Loc) const;
226
227
  /// Equivalent to `getValue(getStorageLocation(D, SP), SkipPast::None)` if `D`
228
  /// is assigned a storage location in the environment, otherwise returns null.
229
  Value *getValue(const ValueDecl &D, SkipPast SP) const;
230
231
  /// Equivalent to `getValue(getStorageLocation(E, SP), SkipPast::None)` if `E`
232
  /// is assigned a storage location in the environment, otherwise returns null.
233
  Value *getValue(const Expr &E, SkipPast SP) const;
234
235
  /// Transfers ownership of `Loc` to the analysis context and returns a
236
  /// reference to it.
237
  ///
238
  /// Requirements:
239
  ///
240
  ///  `Loc` must not be null.
241
  template <typename T>
242
  typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type
243
  takeOwnership(std::unique_ptr<T> Loc) {
244
    return DACtx->takeOwnership(std::move(Loc));
245
  }
246
247
  /// Transfers ownership of `Val` to the analysis context and returns a
248
  /// reference to it.
249
  ///
250
  /// Requirements:
251
  ///
252
  ///  `Val` must not be null.
253
  template <typename T>
254
  typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type
255
4.50k
  takeOwnership(std::unique_ptr<T> Val) {
256
4.50k
    return DACtx->takeOwnership(std::move(Val));
257
4.50k
  }
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::IntegerValue>::value, clang::dataflow::IntegerValue&>::type clang::dataflow::Environment::takeOwnership<clang::dataflow::IntegerValue>(std::__1::unique_ptr<clang::dataflow::IntegerValue, std::__1::default_delete<clang::dataflow::IntegerValue> >)
Line
Count
Source
255
611
  takeOwnership(std::unique_ptr<T> Val) {
256
611
    return DACtx->takeOwnership(std::move(Val));
257
611
  }
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::ReferenceValue>::value, clang::dataflow::ReferenceValue&>::type clang::dataflow::Environment::takeOwnership<clang::dataflow::ReferenceValue>(std::__1::unique_ptr<clang::dataflow::ReferenceValue, std::__1::default_delete<clang::dataflow::ReferenceValue> >)
Line
Count
Source
255
2.21k
  takeOwnership(std::unique_ptr<T> Val) {
256
2.21k
    return DACtx->takeOwnership(std::move(Val));
257
2.21k
  }
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::PointerValue>::value, clang::dataflow::PointerValue&>::type clang::dataflow::Environment::takeOwnership<clang::dataflow::PointerValue>(std::__1::unique_ptr<clang::dataflow::PointerValue, std::__1::default_delete<clang::dataflow::PointerValue> >)
Line
Count
Source
255
125
  takeOwnership(std::unique_ptr<T> Val) {
256
125
    return DACtx->takeOwnership(std::move(Val));
257
125
  }
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::StructValue>::value, clang::dataflow::StructValue&>::type clang::dataflow::Environment::takeOwnership<clang::dataflow::StructValue>(std::__1::unique_ptr<clang::dataflow::StructValue, std::__1::default_delete<clang::dataflow::StructValue> >)
Line
Count
Source
255
1.54k
  takeOwnership(std::unique_ptr<T> Val) {
256
1.54k
    return DACtx->takeOwnership(std::move(Val));
257
1.54k
  }
258
259
  /// Returns a symbolic boolean value that models a boolean literal equal to
260
  /// `Value`
261
454
  AtomicBoolValue &getBoolLiteralValue(bool Value) const {
262
454
    return DACtx->getBoolLiteralValue(Value);
263
454
  }
264
265
  /// Returns an atomic boolean value.
266
696
  BoolValue &makeAtomicBoolValue() const {
267
696
    return DACtx->createAtomicBoolValue();
268
696
  }
269
270
  /// Returns a boolean value that represents the conjunction of `LHS` and
271
  /// `RHS`. Subsequent calls with the same arguments, regardless of their
272
  /// order, will return the same result. If the given boolean values represent
273
  /// the same value, the result will be the value itself.
274
184
  BoolValue &makeAnd(BoolValue &LHS, BoolValue &RHS) const {
275
184
    return DACtx->getOrCreateConjunction(LHS, RHS);
276
184
  }
277
278
  /// Returns a boolean value that represents the disjunction of `LHS` and
279
  /// `RHS`. Subsequent calls with the same arguments, regardless of their
280
  /// order, will return the same result. If the given boolean values represent
281
  /// the same value, the result will be the value itself.
282
77
  BoolValue &makeOr(BoolValue &LHS, BoolValue &RHS) const {
283
77
    return DACtx->getOrCreateDisjunction(LHS, RHS);
284
77
  }
285
286
  /// Returns a boolean value that represents the negation of `Val`. Subsequent
287
  /// calls with the same argument will return the same result.
288
733
  BoolValue &makeNot(BoolValue &Val) const {
289
733
    return DACtx->getOrCreateNegation(Val);
290
733
  }
291
292
  /// Returns a boolean value represents `LHS` => `RHS`. Subsequent calls with
293
  /// the same arguments, will return the same result. If the given boolean
294
  /// values represent the same value, the result will be a value that
295
  /// represents the true boolean literal.
296
30
  BoolValue &makeImplication(BoolValue &LHS, BoolValue &RHS) const {
297
30
    return DACtx->getOrCreateImplication(LHS, RHS);
298
30
  }
299
300
  /// Returns a boolean value represents `LHS` <=> `RHS`. Subsequent calls with
301
  /// the same arguments, regardless of their order, will return the same
302
  /// result. If the given boolean values represent the same value, the result
303
  /// will be a value that represents the true boolean literal.
304
124
  BoolValue &makeIff(BoolValue &LHS, BoolValue &RHS) const {
305
124
    return DACtx->getOrCreateIff(LHS, RHS);
306
124
  }
307
308
  /// Returns the token that identifies the flow condition of the environment.
309
108
  AtomicBoolValue &getFlowConditionToken() const { return *FlowConditionToken; }
310
311
  /// Builds and returns the logical formula defining the flow condition
312
  /// identified by `Token`. If a value in the formula is present as a key in
313
  /// `Substitutions`, it will be substituted with the value it maps to.
314
  BoolValue &buildAndSubstituteFlowCondition(
315
      AtomicBoolValue &Token,
316
0
      llvm::DenseMap<AtomicBoolValue *, BoolValue *> Substitutions) {
317
0
    return DACtx->buildAndSubstituteFlowCondition(Token,
318
0
                                                  std::move(Substitutions));
319
0
  }
320
321
  /// Adds `Val` to the set of clauses that constitute the flow condition.
322
  void addToFlowCondition(BoolValue &Val);
323
324
  /// Returns true if and only if the clauses that constitute the flow condition
325
  /// imply that `Val` is true.
326
  bool flowConditionImplies(BoolValue &Val) const;
327
328
private:
329
  /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
330
  /// return null.
331
  ///
332
  /// Recursively initializes storage locations and values until it sees a
333
  /// self-referential pointer or reference type. `Visited` is used to track
334
  /// which types appeared in the reference/pointer chain in order to avoid
335
  /// creating a cyclic dependency with self-referential pointers/references.
336
  ///
337
  /// Requirements:
338
  ///
339
  ///  `Type` must not be null.
340
  Value *createValueUnlessSelfReferential(QualType Type,
341
                                          llvm::DenseSet<QualType> &Visited,
342
                                          int Depth, int &CreatedValuesCount);
343
344
  StorageLocation &skip(StorageLocation &Loc, SkipPast SP) const;
345
  const StorageLocation &skip(const StorageLocation &Loc, SkipPast SP) const;
346
347
  // `DACtx` is not null and not owned by this object.
348
  DataflowAnalysisContext *DACtx;
349
350
  // Maps from program declarations and statements to storage locations that are
351
  // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these
352
  // include only storage locations that are in scope for a particular basic
353
  // block.
354
  llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
355
  llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
356
357
  llvm::DenseMap<const StorageLocation *, Value *> LocToVal;
358
359
  // Maps locations of struct members to symbolic values of the structs that own
360
  // them and the decls of the struct members.
361
  llvm::DenseMap<const StorageLocation *,
362
                 std::pair<StructValue *, const ValueDecl *>>
363
      MemberLocToStruct;
364
365
  AtomicBoolValue *FlowConditionToken;
366
};
367
368
} // namespace dataflow
369
} // namespace clang
370
371
#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H