1341825Sdim//===- BugReporterVisitors.h - Generate PathDiagnostics ---------*- C++ -*-===// 2326941Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6326941Sdim// 7326941Sdim//===----------------------------------------------------------------------===// 8326941Sdim// 9326941Sdim// This file declares BugReporterVisitors, which are used to generate enhanced 10326941Sdim// diagnostic traces. 11326941Sdim// 12326941Sdim//===----------------------------------------------------------------------===// 13326941Sdim 14326941Sdim#ifndef LLVM_CLANG_STATICANALYZER_CORE_BUGREPORTER_BUGREPORTERVISITORS_H 15326941Sdim#define LLVM_CLANG_STATICANALYZER_CORE_BUGREPORTER_BUGREPORTERVISITORS_H 16326941Sdim 17353358Sdim#include "clang/Analysis/ProgramPoint.h" 18341825Sdim#include "clang/Basic/LLVM.h" 19341825Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h" 20326941Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 21326941Sdim#include "llvm/ADT/FoldingSet.h" 22341825Sdim#include "llvm/ADT/STLExtras.h" 23341825Sdim#include "llvm/ADT/StringRef.h" 24341825Sdim#include <memory> 25326941Sdim 26326941Sdimnamespace clang { 27341825Sdim 28341825Sdimclass BinaryOperator; 29326941Sdimclass CFGBlock; 30341825Sdimclass DeclRefExpr; 31341825Sdimclass Expr; 32341825Sdimclass Stmt; 33326941Sdim 34326941Sdimnamespace ento { 35326941Sdim 36360784Sdimclass PathSensitiveBugReport; 37326941Sdimclass BugReporterContext; 38326941Sdimclass ExplodedNode; 39326941Sdimclass MemRegion; 40326941Sdimclass PathDiagnosticPiece; 41360784Sdimusing PathDiagnosticPieceRef = std::shared_ptr<PathDiagnosticPiece>; 42326941Sdim 43341825Sdim/// BugReporterVisitors are used to add custom diagnostics along a path. 44326941Sdimclass BugReporterVisitor : public llvm::FoldingSetNode { 45326941Sdimpublic: 46326941Sdim BugReporterVisitor() = default; 47326941Sdim BugReporterVisitor(const BugReporterVisitor &) = default; 48326941Sdim BugReporterVisitor(BugReporterVisitor &&) {} 49326941Sdim virtual ~BugReporterVisitor(); 50326941Sdim 51341825Sdim /// Return a diagnostic piece which should be associated with the 52326941Sdim /// given node. 53341825Sdim /// Note that this function does *not* get run on the very last node 54341825Sdim /// of the report, as the PathDiagnosticPiece associated with the 55341825Sdim /// last node should be unique. 56341825Sdim /// Use {@code getEndPath} to customize the note associated with the report 57341825Sdim /// end instead. 58326941Sdim /// 59326941Sdim /// The last parameter can be used to register a new visitor with the given 60326941Sdim /// BugReport while processing a node. 61360784Sdim virtual PathDiagnosticPieceRef VisitNode(const ExplodedNode *Succ, 62360784Sdim BugReporterContext &BRC, 63360784Sdim PathSensitiveBugReport &BR) = 0; 64326941Sdim 65341825Sdim /// Last function called on the visitor, no further calls to VisitNode 66341825Sdim /// would follow. 67341825Sdim virtual void finalizeVisitor(BugReporterContext &BRC, 68341825Sdim const ExplodedNode *EndPathNode, 69360784Sdim PathSensitiveBugReport &BR); 70341825Sdim 71341825Sdim /// Provide custom definition for the final diagnostic piece on the 72326941Sdim /// path - the piece, which is displayed before the path is expanded. 73326941Sdim /// 74341825Sdim /// NOTE that this function can be implemented on at most one used visitor, 75341825Sdim /// and otherwise it crahes at runtime. 76360784Sdim virtual PathDiagnosticPieceRef getEndPath(BugReporterContext &BRC, 77360784Sdim const ExplodedNode *N, 78360784Sdim PathSensitiveBugReport &BR); 79326941Sdim 80326941Sdim virtual void Profile(llvm::FoldingSetNodeID &ID) const = 0; 81326941Sdim 82341825Sdim /// Generates the default final diagnostic piece. 83360784Sdim static PathDiagnosticPieceRef 84360784Sdim getDefaultEndPath(const BugReporterContext &BRC, const ExplodedNode *N, 85360784Sdim const PathSensitiveBugReport &BR); 86326941Sdim}; 87326941Sdim 88360784Sdimnamespace bugreporter { 89360784Sdim 90360784Sdim/// Specifies the type of tracking for an expression. 91360784Sdimenum class TrackingKind { 92360784Sdim /// Default tracking kind -- specifies that as much information should be 93360784Sdim /// gathered about the tracked expression value as possible. 94360784Sdim Thorough, 95360784Sdim /// Specifies that a more moderate tracking should be used for the expression 96360784Sdim /// value. This will essentially make sure that functions relevant to the it 97360784Sdim /// aren't pruned, but otherwise relies on the user reading the code or 98360784Sdim /// following the arrows. 99360784Sdim Condition 100360784Sdim}; 101360784Sdim 102360784Sdim/// Attempts to add visitors to track expression value back to its point of 103360784Sdim/// origin. 104360784Sdim/// 105360784Sdim/// \param N A node "downstream" from the evaluation of the statement. 106360784Sdim/// \param E The expression value which we are tracking 107360784Sdim/// \param R The bug report to which visitors should be attached. 108360784Sdim/// \param EnableNullFPSuppression Whether we should employ false positive 109360784Sdim/// suppression (inlined defensive checks, returned null). 110360784Sdim/// 111360784Sdim/// \return Whether or not the function was able to add visitors for this 112360784Sdim/// statement. Note that returning \c true does not actually imply 113360784Sdim/// that any visitors were added. 114360784Sdimbool trackExpressionValue(const ExplodedNode *N, const Expr *E, 115360784Sdim PathSensitiveBugReport &R, 116360784Sdim TrackingKind TKind = TrackingKind::Thorough, 117360784Sdim bool EnableNullFPSuppression = true); 118360784Sdim 119360784Sdimconst Expr *getDerefExpr(const Stmt *S); 120360784Sdim 121360784Sdim} // namespace bugreporter 122360784Sdim 123344779Sdim/// Finds last store into the given region, 124344779Sdim/// which is different from a given symbolic value. 125341825Sdimclass FindLastStoreBRVisitor final : public BugReporterVisitor { 126326941Sdim const MemRegion *R; 127326941Sdim SVal V; 128341825Sdim bool Satisfied = false; 129326941Sdim 130326941Sdim /// If the visitor is tracking the value directly responsible for the 131326941Sdim /// bug, we are going to employ false positive suppression. 132326941Sdim bool EnableNullFPSuppression; 133326941Sdim 134360784Sdim using TrackingKind = bugreporter::TrackingKind; 135360784Sdim TrackingKind TKind; 136360784Sdim const StackFrameContext *OriginSFC; 137360784Sdim 138326941Sdimpublic: 139360784Sdim /// \param V We're searching for the store where \c R received this value. 140360784Sdim /// \param R The region we're tracking. 141360784Sdim /// \param TKind May limit the amount of notes added to the bug report. 142360784Sdim /// \param OriginSFC Only adds notes when the last store happened in a 143360784Sdim /// different stackframe to this one. Disregarded if the tracking kind 144360784Sdim /// is thorough. 145360784Sdim /// This is useful, because for non-tracked regions, notes about 146360784Sdim /// changes to its value in a nested stackframe could be pruned, and 147360784Sdim /// this visitor can prevent that without polluting the bugpath too 148360784Sdim /// much. 149326941Sdim FindLastStoreBRVisitor(KnownSVal V, const MemRegion *R, 150360784Sdim bool InEnableNullFPSuppression, TrackingKind TKind, 151360784Sdim const StackFrameContext *OriginSFC = nullptr) 152360784Sdim : R(R), V(V), EnableNullFPSuppression(InEnableNullFPSuppression), 153360784Sdim TKind(TKind), OriginSFC(OriginSFC) { 154360784Sdim assert(R); 155360784Sdim } 156326941Sdim 157326941Sdim void Profile(llvm::FoldingSetNodeID &ID) const override; 158326941Sdim 159360784Sdim PathDiagnosticPieceRef VisitNode(const ExplodedNode *N, 160360784Sdim BugReporterContext &BRC, 161360784Sdim PathSensitiveBugReport &BR) override; 162326941Sdim}; 163326941Sdim 164341825Sdimclass TrackConstraintBRVisitor final : public BugReporterVisitor { 165326941Sdim DefinedSVal Constraint; 166326941Sdim bool Assumption; 167341825Sdim bool IsSatisfied = false; 168326941Sdim bool IsZeroCheck; 169326941Sdim 170326941Sdim /// We should start tracking from the last node along the path in which the 171326941Sdim /// value is constrained. 172341825Sdim bool IsTrackingTurnedOn = false; 173326941Sdim 174326941Sdimpublic: 175326941Sdim TrackConstraintBRVisitor(DefinedSVal constraint, bool assumption) 176341825Sdim : Constraint(constraint), Assumption(assumption), 177341825Sdim IsZeroCheck(!Assumption && Constraint.getAs<Loc>()) {} 178326941Sdim 179326941Sdim void Profile(llvm::FoldingSetNodeID &ID) const override; 180326941Sdim 181326941Sdim /// Return the tag associated with this visitor. This tag will be used 182326941Sdim /// to make all PathDiagnosticPieces created by this visitor. 183326941Sdim static const char *getTag(); 184326941Sdim 185360784Sdim PathDiagnosticPieceRef VisitNode(const ExplodedNode *N, 186360784Sdim BugReporterContext &BRC, 187360784Sdim PathSensitiveBugReport &BR) override; 188326941Sdim 189326941Sdimprivate: 190326941Sdim /// Checks if the constraint is valid in the current state. 191326941Sdim bool isUnderconstrained(const ExplodedNode *N) const; 192326941Sdim}; 193326941Sdim 194326941Sdim/// \class NilReceiverBRVisitor 195341825Sdim/// Prints path notes when a message is sent to a nil receiver. 196341825Sdimclass NilReceiverBRVisitor final : public BugReporterVisitor { 197326941Sdimpublic: 198326941Sdim void Profile(llvm::FoldingSetNodeID &ID) const override { 199326941Sdim static int x = 0; 200326941Sdim ID.AddPointer(&x); 201326941Sdim } 202326941Sdim 203360784Sdim PathDiagnosticPieceRef VisitNode(const ExplodedNode *N, 204360784Sdim BugReporterContext &BRC, 205360784Sdim PathSensitiveBugReport &BR) override; 206326941Sdim 207326941Sdim /// If the statement is a message send expression with nil receiver, returns 208326941Sdim /// the receiver expression. Returns NULL otherwise. 209326941Sdim static const Expr *getNilReceiver(const Stmt *S, const ExplodedNode *N); 210326941Sdim}; 211326941Sdim 212326941Sdim/// Visitor that tries to report interesting diagnostics from conditions. 213341825Sdimclass ConditionBRVisitor final : public BugReporterVisitor { 214326941Sdim // FIXME: constexpr initialization isn't supported by MSVC2013. 215360784Sdim constexpr static llvm::StringLiteral GenericTrueMessage = 216360784Sdim "Assuming the condition is true"; 217360784Sdim constexpr static llvm::StringLiteral GenericFalseMessage = 218360784Sdim "Assuming the condition is false"; 219326941Sdim 220326941Sdimpublic: 221326941Sdim void Profile(llvm::FoldingSetNodeID &ID) const override { 222326941Sdim static int x = 0; 223326941Sdim ID.AddPointer(&x); 224326941Sdim } 225326941Sdim 226326941Sdim /// Return the tag associated with this visitor. This tag will be used 227326941Sdim /// to make all PathDiagnosticPieces created by this visitor. 228326941Sdim static const char *getTag(); 229326941Sdim 230360784Sdim PathDiagnosticPieceRef VisitNode(const ExplodedNode *N, 231360784Sdim BugReporterContext &BRC, 232360784Sdim PathSensitiveBugReport &BR) override; 233326941Sdim 234360784Sdim PathDiagnosticPieceRef VisitNodeImpl(const ExplodedNode *N, 235360784Sdim BugReporterContext &BRC, 236360784Sdim PathSensitiveBugReport &BR); 237326941Sdim 238360784Sdim PathDiagnosticPieceRef 239326941Sdim VisitTerminator(const Stmt *Term, const ExplodedNode *N, 240360784Sdim const CFGBlock *SrcBlk, const CFGBlock *DstBlk, 241360784Sdim PathSensitiveBugReport &R, BugReporterContext &BRC); 242326941Sdim 243360784Sdim PathDiagnosticPieceRef VisitTrueTest(const Expr *Cond, 244360784Sdim BugReporterContext &BRC, 245360784Sdim PathSensitiveBugReport &R, 246360784Sdim const ExplodedNode *N, bool TookTrue); 247326941Sdim 248360784Sdim PathDiagnosticPieceRef VisitTrueTest(const Expr *Cond, const DeclRefExpr *DR, 249360784Sdim BugReporterContext &BRC, 250360784Sdim PathSensitiveBugReport &R, 251360784Sdim const ExplodedNode *N, bool TookTrue, 252360784Sdim bool IsAssuming); 253326941Sdim 254360784Sdim PathDiagnosticPieceRef 255326941Sdim VisitTrueTest(const Expr *Cond, const BinaryOperator *BExpr, 256360784Sdim BugReporterContext &BRC, PathSensitiveBugReport &R, 257360784Sdim const ExplodedNode *N, bool TookTrue, bool IsAssuming); 258326941Sdim 259360784Sdim PathDiagnosticPieceRef VisitTrueTest(const Expr *Cond, const MemberExpr *ME, 260360784Sdim BugReporterContext &BRC, 261360784Sdim PathSensitiveBugReport &R, 262360784Sdim const ExplodedNode *N, bool TookTrue, 263360784Sdim bool IsAssuming); 264353358Sdim 265360784Sdim PathDiagnosticPieceRef 266326941Sdim VisitConditionVariable(StringRef LhsString, const Expr *CondVarExpr, 267360784Sdim BugReporterContext &BRC, PathSensitiveBugReport &R, 268353358Sdim const ExplodedNode *N, bool TookTrue); 269326941Sdim 270353358Sdim /// Tries to print the value of the given expression. 271353358Sdim /// 272353358Sdim /// \param CondVarExpr The expression to print its value. 273353358Sdim /// \param Out The stream to print. 274353358Sdim /// \param N The node where we encountered the condition. 275353358Sdim /// \param TookTrue Whether we took the \c true branch of the condition. 276353358Sdim /// 277353358Sdim /// \return Whether the print was successful. (The printing is successful if 278353358Sdim /// we model the value and we could obtain it.) 279353358Sdim bool printValue(const Expr *CondVarExpr, raw_ostream &Out, 280353358Sdim const ExplodedNode *N, bool TookTrue, bool IsAssuming); 281353358Sdim 282326941Sdim bool patternMatch(const Expr *Ex, 283326941Sdim const Expr *ParentEx, 284326941Sdim raw_ostream &Out, 285326941Sdim BugReporterContext &BRC, 286360784Sdim PathSensitiveBugReport &R, 287326941Sdim const ExplodedNode *N, 288353358Sdim Optional<bool> &prunable, 289353358Sdim bool IsSameFieldName); 290326941Sdim 291326941Sdim static bool isPieceMessageGeneric(const PathDiagnosticPiece *Piece); 292326941Sdim}; 293326941Sdim 294341825Sdim/// Suppress reports that might lead to known false positives. 295326941Sdim/// 296326941Sdim/// Currently this suppresses reports based on locations of bugs. 297326941Sdimclass LikelyFalsePositiveSuppressionBRVisitor final 298341825Sdim : public BugReporterVisitor { 299326941Sdimpublic: 300326941Sdim static void *getTag() { 301326941Sdim static int Tag = 0; 302326941Sdim return static_cast<void *>(&Tag); 303326941Sdim } 304326941Sdim 305326941Sdim void Profile(llvm::FoldingSetNodeID &ID) const override { 306326941Sdim ID.AddPointer(getTag()); 307326941Sdim } 308326941Sdim 309360784Sdim PathDiagnosticPieceRef VisitNode(const ExplodedNode *, BugReporterContext &, 310360784Sdim PathSensitiveBugReport &) override { 311326941Sdim return nullptr; 312326941Sdim } 313326941Sdim 314341825Sdim void finalizeVisitor(BugReporterContext &BRC, const ExplodedNode *N, 315360784Sdim PathSensitiveBugReport &BR) override; 316326941Sdim}; 317326941Sdim 318341825Sdim/// When a region containing undefined value or '0' value is passed 319326941Sdim/// as an argument in a call, marks the call as interesting. 320326941Sdim/// 321326941Sdim/// As a result, BugReporter will not prune the path through the function even 322326941Sdim/// if the region's contents are not modified/accessed by the call. 323341825Sdimclass UndefOrNullArgVisitor final : public BugReporterVisitor { 324326941Sdim /// The interesting memory region this visitor is tracking. 325326941Sdim const MemRegion *R; 326326941Sdim 327326941Sdimpublic: 328326941Sdim UndefOrNullArgVisitor(const MemRegion *InR) : R(InR) {} 329326941Sdim 330326941Sdim void Profile(llvm::FoldingSetNodeID &ID) const override { 331326941Sdim static int Tag = 0; 332326941Sdim ID.AddPointer(&Tag); 333326941Sdim ID.AddPointer(R); 334326941Sdim } 335326941Sdim 336360784Sdim PathDiagnosticPieceRef VisitNode(const ExplodedNode *N, 337360784Sdim BugReporterContext &BRC, 338360784Sdim PathSensitiveBugReport &BR) override; 339326941Sdim}; 340326941Sdim 341341825Sdimclass SuppressInlineDefensiveChecksVisitor final : public BugReporterVisitor { 342326941Sdim /// The symbolic value for which we are tracking constraints. 343326941Sdim /// This value is constrained to null in the end of path. 344326941Sdim DefinedSVal V; 345326941Sdim 346326941Sdim /// Track if we found the node where the constraint was first added. 347341825Sdim bool IsSatisfied = false; 348326941Sdim 349326941Sdim /// Since the visitors can be registered on nodes previous to the last 350326941Sdim /// node in the BugReport, but the path traversal always starts with the last 351326941Sdim /// node, the visitor invariant (that we start with a node in which V is null) 352326941Sdim /// might not hold when node visitation starts. We are going to start tracking 353326941Sdim /// from the last node in which the value is null. 354341825Sdim bool IsTrackingTurnedOn = false; 355326941Sdim 356326941Sdimpublic: 357326941Sdim SuppressInlineDefensiveChecksVisitor(DefinedSVal Val, const ExplodedNode *N); 358326941Sdim 359326941Sdim void Profile(llvm::FoldingSetNodeID &ID) const override; 360326941Sdim 361326941Sdim /// Return the tag associated with this visitor. This tag will be used 362326941Sdim /// to make all PathDiagnosticPieces created by this visitor. 363326941Sdim static const char *getTag(); 364326941Sdim 365360784Sdim PathDiagnosticPieceRef VisitNode(const ExplodedNode *Succ, 366360784Sdim BugReporterContext &BRC, 367360784Sdim PathSensitiveBugReport &BR) override; 368326941Sdim}; 369326941Sdim 370341825Sdim/// The bug visitor will walk all the nodes in a path and collect all the 371341825Sdim/// constraints. When it reaches the root node, will create a refutation 372341825Sdim/// manager and check if the constraints are satisfiable 373341825Sdimclass FalsePositiveRefutationBRVisitor final : public BugReporterVisitor { 374341825Sdimprivate: 375341825Sdim /// Holds the constraints in a given path 376341825Sdim ConstraintRangeTy Constraints; 377341825Sdim 378341825Sdimpublic: 379341825Sdim FalsePositiveRefutationBRVisitor(); 380341825Sdim 381341825Sdim void Profile(llvm::FoldingSetNodeID &ID) const override; 382341825Sdim 383360784Sdim PathDiagnosticPieceRef VisitNode(const ExplodedNode *N, 384360784Sdim BugReporterContext &BRC, 385360784Sdim PathSensitiveBugReport &BR) override; 386341825Sdim 387341825Sdim void finalizeVisitor(BugReporterContext &BRC, const ExplodedNode *EndPathNode, 388360784Sdim PathSensitiveBugReport &BR) override; 389341825Sdim}; 390341825Sdim 391353358Sdim 392353358Sdim/// The visitor detects NoteTags and displays the event notes they contain. 393353358Sdimclass TagVisitor : public BugReporterVisitor { 394353358Sdimpublic: 395353358Sdim void Profile(llvm::FoldingSetNodeID &ID) const override; 396353358Sdim 397360784Sdim PathDiagnosticPieceRef VisitNode(const ExplodedNode *N, 398360784Sdim BugReporterContext &BRC, 399360784Sdim PathSensitiveBugReport &R) override; 400353358Sdim}; 401353358Sdim 402341825Sdim} // namespace ento 403326941Sdim 404341825Sdim} // namespace clang 405326941Sdim 406341825Sdim#endif // LLVM_CLANG_STATICANALYZER_CORE_BUGREPORTER_BUGREPORTERVISITORS_H 407