diff options
Diffstat (limited to 'include/clang/StaticAnalyzer/Core')
36 files changed, 2707 insertions, 1698 deletions
diff --git a/include/clang/StaticAnalyzer/Core/Analyses.def b/include/clang/StaticAnalyzer/Core/Analyses.def index 281a2ac3a66f..99e26c75e1c2 100644 --- a/include/clang/StaticAnalyzer/Core/Analyses.def +++ b/include/clang/StaticAnalyzer/Core/Analyses.def @@ -33,6 +33,7 @@ ANALYSIS_DIAGNOSTICS(HTML_SINGLE_FILE, "html-single-file", "Output analysis resu ANALYSIS_DIAGNOSTICS(PLIST, "plist", "Output analysis results using Plists", createPlistDiagnosticConsumer) ANALYSIS_DIAGNOSTICS(PLIST_MULTI_FILE, "plist-multi-file", "Output analysis results using Plists (allowing for multi-file bugs)", createPlistMultiFileDiagnosticConsumer) ANALYSIS_DIAGNOSTICS(PLIST_HTML, "plist-html", "Output analysis results using HTML wrapped with Plists", createPlistHTMLDiagnosticConsumer) +ANALYSIS_DIAGNOSTICS(SARIF, "sarif", "Output analysis results in a SARIF file", createSarifDiagnosticConsumer) ANALYSIS_DIAGNOSTICS(TEXT, "text", "Text output of analysis results", createTextPathDiagnosticConsumer) #ifndef ANALYSIS_PURGE diff --git a/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def b/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def new file mode 100644 index 000000000000..3cd54df7b179 --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def @@ -0,0 +1,377 @@ +//===-- AnalyzerOptions.def - Metadata about Static Analyses ----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the analyzer options avaible with -analyzer-config. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_STRINGREF_H +#error This .def file is expected to be included in translation units where \ +"llvm/ADT/StringRef.h" is already included! +#endif + +#ifdef ANALYZER_OPTION +#ifndef ANALYZER_OPTION_DEPENDS_ON_USER_MODE +#error If you didnt include this file with the intent of generating methods, \ +define both 'ANALYZER_OPTION' and 'ANALYZER_OPTION_DEPENDS_ON_USER_MODE' macros! +#endif +#endif + +#ifndef ANALYZER_OPTION_DEPENDS_ON_USER_MODE +#ifdef ANALYZER_OPTION +#error If you didnt include this file with the intent of generating methods, \ +define both 'ANALYZER_OPTION' and 'ANALYZER_OPTION_DEPENDS_ON_USER_MODE' macros! +#endif +#endif + +#ifndef ANALYZER_OPTION +/// Create a new analyzer option, but dont generate a method for it in +/// AnalyzerOptions. +/// +/// TYPE - The type of the option object that will be stored in +/// AnalyzerOptions. This file is expected to be icluded in translation +/// units where AnalyzerOptions.h is included, so types from that +/// header should be used. +/// NAME - The name of the option object. +/// CMDFLAG - The command line flag for the option. +/// (-analyzer-config CMDFLAG=VALUE) +/// DESC - Description of the flag. +/// DEFAULT_VAL - The default value for CMDFLAG. +#define ANALYZER_OPTION(TYPE, NAME, CMDFLAG, DESC, DEFAULT_VAL) +#endif + +#ifndef ANALYZER_OPTION_DEPENDS_ON_USER_MODE +/// Create a new analyzer option, but dont generate a method for it in +/// AnalyzerOptions. It's value depends on the option "user-mode". +/// +/// TYPE - The type of the option object that will be stored in +/// AnalyzerOptions. This file is expected to be icluded in translation +/// units where AnalyzerOptions.h is included, so types from that +/// header should be used. +/// NAME - The name of the option object. +/// CMDFLAG - The command line flag for the option. +/// (-analyzer-config CMDFLAG=VALUE) +/// DESC - Description of the flag. +/// SHALLOW_VAL - The default value for CMDFLAG, when "user-mode" was set to +/// "shallow". +/// DEEP_VAL - The default value for CMDFLAG, when "user-mode" was set to +/// "deep". +#define ANALYZER_OPTION_DEPENDS_ON_USER_MODE(TYPE, NAME, CMDFLAG, DESC, \ + SHALLOW_VAL, DEEP_VAL) +#endif + +//===----------------------------------------------------------------------===// +// The "mode" option. Since some options depend on this, we list it on top of +// this file in order to make sure that the generated field for it is +// initialized before the rest. +//===----------------------------------------------------------------------===// + +ANALYZER_OPTION( + StringRef, UserMode, "mode", + "(string) Controls the high-level analyzer mode, which influences the " + "default settings for some of the lower-level config options (such as " + "IPAMode). Value: \"deep\", \"shallow\".", + "deep") + +//===----------------------------------------------------------------------===// +// Boolean analyzer options. +//===----------------------------------------------------------------------===// + +ANALYZER_OPTION(bool, ShouldIncludeImplicitDtorsInCFG, "cfg-implicit-dtors", + "Whether or not implicit destructors for C++ objects " + "should be included in the CFG.", + true) + +ANALYZER_OPTION(bool, ShouldIncludeTemporaryDtorsInCFG, "cfg-temporary-dtors", + "Whether or not the destructors for C++ temporary " + "objects should be included in the CFG.", + true) + +ANALYZER_OPTION( + bool, ShouldIncludeLifetimeInCFG, "cfg-lifetime", + "Whether or not end-of-lifetime information should be included in the CFG.", + false) + +ANALYZER_OPTION(bool, ShouldIncludeLoopExitInCFG, "cfg-loopexit", + "Whether or not the end of the loop information should " + "be included in the CFG.", + false) + +ANALYZER_OPTION(bool, ShouldIncludeRichConstructorsInCFG, + "cfg-rich-constructors", + "Whether or not construction site information should be " + "included in the CFG C++ constructor elements.", + true) + +ANALYZER_OPTION( + bool, ShouldIncludeScopesInCFG, "cfg-scopes", + "Whether or not scope information should be included in the CFG.", false) + +ANALYZER_OPTION( + bool, MayInlineTemplateFunctions, "c++-template-inlining", + "Whether or not templated functions may be considered for inlining.", true) + +ANALYZER_OPTION(bool, MayInlineCXXStandardLibrary, "c++-stdlib-inlining", + "Whether or not C++ standard library functions may be " + "considered for inlining.", + true) + +ANALYZER_OPTION(bool, MayInlineCXXAllocator, "c++-allocator-inlining", + "Whether or not allocator call may be considered for inlining.", + true) + +ANALYZER_OPTION( + bool, MayInlineCXXSharedPtrDtor, "c++-shared_ptr-inlining", + "Whether or not the destructor of C++ 'shared_ptr' may be considered for " + "inlining. This covers std::shared_ptr, std::tr1::shared_ptr, and " + "boost::shared_ptr, and indeed any destructor named '~shared_ptr'.", + false) + +ANALYZER_OPTION(bool, MayInlineCXXTemporaryDtors, "c++-temp-dtor-inlining", + "Whether C++ temporary destructors should be inlined " + "during analysis. If temporary destructors are disabled " + "in the CFG via the 'cfg-temporary-dtors' option, " + "temporary destructors would not be inlined anyway.", + true) + +ANALYZER_OPTION( + bool, ShouldSuppressNullReturnPaths, "suppress-null-return-paths", + "Whether or not paths that go through null returns should be suppressed. " + "This is a heuristic for avoiding bug reports with paths that go through " + "inlined functions that are more defensive than their callers.", + true) + +ANALYZER_OPTION( + bool, ShouldAvoidSuppressingNullArgumentPaths, + "avoid-suppressing-null-argument-paths", + "Whether a bug report should not be suppressed if its path includes a call " + "with a null argument, even if that call has a null return. This option " + "has no effect when ShouldSuppressNullReturnPaths is false. This is a " + "counter-heuristic to avoid false negatives.", + false) + +ANALYZER_OPTION(bool, ShouldSuppressInlinedDefensiveChecks, + "suppress-inlined-defensive-checks", + "Whether or not diagnostics containing inlined " + "defensive NULL checks should be suppressed.", + true) + +ANALYZER_OPTION(bool, MayInlineCXXContainerMethods, "c++-container-inlining", + "Whether or not methods of C++ container objects may be " + "considered for inlining.", + false) + +ANALYZER_OPTION(bool, ShouldSuppressFromCXXStandardLibrary, + "suppress-c++-stdlib", + "Whether or not diagnostics reported within the C++ " + "standard library should be suppressed.", + true) + +ANALYZER_OPTION(bool, ShouldCrosscheckWithZ3, "crosscheck-with-z3", + "Whether bug reports should be crosschecked with the Z3 " + "constraint manager backend.", + false) + +ANALYZER_OPTION(bool, ShouldReportIssuesInMainSourceFile, + "report-in-main-source-file", + "Whether or not the diagnostic report should be always " + "reported in the main source file and not the headers.", + false) + +ANALYZER_OPTION(bool, ShouldWriteStableReportFilename, "stable-report-filename", + "Whether or not the report filename should be random or not.", + false) + +ANALYZER_OPTION( + bool, ShouldSerializeStats, "serialize-stats", + "Whether the analyzer should serialize statistics to plist output. " + "Statistics would be serialized in JSON format inside the main dictionary " + "under the statistics key. Available only if compiled in assert mode or " + "with LLVM statistics explicitly enabled.", + false) + +ANALYZER_OPTION(bool, MayInlineObjCMethod, "objc-inlining", + "Whether ObjectiveC inlining is enabled, false otherwise.", + true) + +ANALYZER_OPTION(bool, ShouldPrunePaths, "prune-paths", + "Whether irrelevant parts of a bug report path should " + "be pruned out of the final output.", + true) + +ANALYZER_OPTION( + bool, ShouldConditionalizeStaticInitializers, + "cfg-conditional-static-initializers", + "Whether 'static' initializers should be in conditional logic in the CFG.", + true) + +ANALYZER_OPTION(bool, ShouldSynthesizeBodies, "faux-bodies", + "Whether the analyzer engine should synthesize fake " + "bodies for well-known functions.", + true) + +ANALYZER_OPTION( + bool, ShouldElideConstructors, "elide-constructors", + "Whether elidable C++ copy-constructors and move-constructors should be " + "actually elided during analysis. Both behaviors are allowed by the C++ " + "standard, and the analyzer, like CodeGen, defaults to eliding. Starting " + "with C++17 some elisions become mandatory, and in these cases the option " + "will be ignored.", + true) + +ANALYZER_OPTION( + bool, ShouldInlineLambdas, "inline-lambdas", + "Whether lambdas should be inlined. Otherwise a sink node will be " + "generated each time a LambdaExpr is visited.", + true) + +ANALYZER_OPTION(bool, ShouldWidenLoops, "widen-loops", + "Whether the analysis should try to widen loops.", false) + +ANALYZER_OPTION( + bool, ShouldUnrollLoops, "unroll-loops", + "Whether the analysis should try to unroll loops with known bounds.", false) + +ANALYZER_OPTION( + bool, ShouldDisplayNotesAsEvents, "notes-as-events", + "Whether the bug reporter should transparently treat extra note diagnostic " + "pieces as event diagnostic pieces. Useful when the diagnostic consumer " + "doesn't support the extra note pieces.", + false) + +ANALYZER_OPTION( + bool, ShouldAggressivelySimplifyBinaryOperation, + "aggressive-binary-operation-simplification", + "Whether SValBuilder should rearrange comparisons and additive operations " + "of symbolic expressions which consist of a sum of a symbol and a concrete " + "integer into the format where symbols are on the left-hand side and the " + "integer is on the right. This is only done if both symbols and both " + "concrete integers are signed, greater than or equal to the quarter of the " + "minimum value of the type and less than or equal to the quarter of the " + "maximum value of that type. A + n <OP> B + m becomes A - B <OP> m - n, " + "where A and B symbolic, n and m are integers. <OP> is any of '==', '!=', " + "'<', '<=', '>', '>=', '+' or '-'. The rearrangement also happens with '-' " + "instead of '+' on either or both side and also if any or both integers " + "are missing.", + false) + +ANALYZER_OPTION( + bool, ShouldEagerlyAssume, "eagerly-assume", + "Whether we should eagerly assume evaluations of conditionals, thus, " + "bifurcating the path. This indicates how the engine should handle " + "expressions such as: 'x = (y != 0)'. When this is true then the " + "subexpression 'y != 0' will be eagerly assumed to be true or false, thus " + "evaluating it to the integers 0 or 1 respectively. The upside is that " + "this can increase analysis precision until we have a better way to lazily " + "evaluate such logic. The downside is that it eagerly bifurcates paths.", + true) + +ANALYZER_OPTION( + bool, IsNaiveCTUEnabled, "experimental-enable-naive-ctu-analysis", + "Whether naive cross translation unit analysis is enabled. This is an " + "experimental feature to inline functions from other translation units.", + false) + +ANALYZER_OPTION(bool, ShouldDisplayMacroExpansions, "expand-macros", + "Whether macros related to the bugpath should be " + "expanded and included in the plist output.", + false) + +ANALYZER_OPTION(bool, DisplayCTUProgress, "display-ctu-progress", + "Whether to emit verbose output about " + "the analyzer's progress related to ctu.", + false) + +//===----------------------------------------------------------------------===// +// Unsinged analyzer options. +//===----------------------------------------------------------------------===// + +ANALYZER_OPTION( + unsigned, AlwaysInlineSize, "ipa-always-inline-size", + "The size of the functions (in basic blocks), which should be considered " + "to be small enough to always inline.", + 3) + +ANALYZER_OPTION( + unsigned, GraphTrimInterval, "graph-trim-interval", + "How often nodes in the ExplodedGraph should be recycled to save memory. " + "To disable node reclamation, set the option to 0.", + 1000) + +ANALYZER_OPTION( + unsigned, MinCFGSizeTreatFunctionsAsLarge, + "min-cfg-size-treat-functions-as-large", + "The number of basic blocks a function needs to have to be considered " + "large for the 'max-times-inline-large' config option.", + 14) + +ANALYZER_OPTION(unsigned, MaxSymbolComplexity, "max-symbol-complexity", + "The maximum complexity of symbolic constraint.", 35) + +ANALYZER_OPTION(unsigned, MaxTimesInlineLarge, "max-times-inline-large", + "The maximum times a large function could be inlined.", 32) + +ANALYZER_OPTION_DEPENDS_ON_USER_MODE( + unsigned, MaxInlinableSize, "max-inlinable-size", + "The bound on the number of basic blocks in an inlined function.", + /* SHALLOW_VAL */ 4, /* DEEP_VAL */ 100) + +ANALYZER_OPTION_DEPENDS_ON_USER_MODE( + unsigned, MaxNodesPerTopLevelFunction, "max-nodes", + "The maximum number of nodes the analyzer can generate while exploring a " + "top level function (for each exploded graph). 0 means no limit.", + /* SHALLOW_VAL */ 75000, /* DEEP_VAL */ 225000) + +ANALYZER_OPTION( + unsigned, RegionStoreSmallStructLimit, "region-store-small-struct-limit", + "The largest number of fields a struct can have and still be considered " + "small This is currently used to decide whether or not it is worth forcing " + "a LazyCompoundVal on bind. To disable all small-struct-dependent " + "behavior, set the option to 0.", + 2) + +//===----------------------------------------------------------------------===// +// String analyzer options. +//===----------------------------------------------------------------------===// + +ANALYZER_OPTION(StringRef, CTUDir, "ctu-dir", + "The directory containing the CTU related files.", "") + +ANALYZER_OPTION(StringRef, CTUIndexName, "ctu-index-name", + "the name of the file containing the CTU index of definitions.", + "externalDefMap.txt") + +ANALYZER_OPTION( + StringRef, ModelPath, "model-path", + "The analyzer can inline an alternative implementation written in C at the " + "call site if the called function's body is not available. This is a path " + "where to look for those alternative implementations (called models).", + "") + +ANALYZER_OPTION( + StringRef, CXXMemberInliningMode, "c++-inlining", + "Controls which C++ member functions will be considered for inlining. " + "Value: \"constructors\", \"destructors\", \"methods\".", + "destructors") + +ANALYZER_OPTION_DEPENDS_ON_USER_MODE( + StringRef, IPAMode, "ipa", + "Controls the mode of inter-procedural analysis. Value: \"none\", " + "\"basic-inlining\", \"inlining\", \"dynamic\", \"dynamic-bifurcate\".", + /* SHALLOW_VAL */ "inlining", /* DEEP_VAL */ "dynamic-bifurcate") + +ANALYZER_OPTION( + StringRef, ExplorationStrategy, "exploration_strategy", + "Value: \"dfs\", \"bfs\", \"unexplored_first\", " + "\"unexplored_first_queue\", \"unexplored_first_location_queue\", " + "\"bfs_block_dfs_contents\".", + "unexplored_first_queue") + +#undef ANALYZER_OPTION_DEPENDS_ON_USER_MODE +#undef ANALYZER_OPTION diff --git a/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h b/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h index 7586f7e0835b..7745e459e19b 100644 --- a/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h +++ b/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h @@ -20,6 +20,7 @@ #include "llvm/ADT/Optional.h" #include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringRef.h" +#include "llvm/ADT/StringSwitch.h" #include <string> #include <utility> #include <vector> @@ -85,7 +86,7 @@ enum CXXInlineableMemberKind { // Uninitialized = 0, /// A dummy mode in which no C++ inlining is enabled. - CIMK_None = 1, + CIMK_None, /// Refers to regular member function and operator calls. CIMK_MemberFunctions, @@ -102,8 +103,6 @@ enum CXXInlineableMemberKind { /// Describes the different modes of inter-procedural analysis. enum IPAKind { - IPAK_NotSet = 0, - /// Perform only intra-procedural analysis. IPAK_None = 1, @@ -121,6 +120,46 @@ enum IPAKind { IPAK_DynamicDispatchBifurcate = 5 }; +enum class ExplorationStrategyKind { + DFS, + BFS, + UnexploredFirst, + UnexploredFirstQueue, + UnexploredFirstLocationQueue, + BFSBlockDFSContents, +}; + +/// Describes the kinds for high-level analyzer mode. +enum UserModeKind { + /// Perform shallow but fast analyzes. + UMK_Shallow = 1, + + /// Perform deep analyzes. + UMK_Deep = 2 +}; + +/// Stores options for the analyzer from the command line. +/// +/// Some options are frontend flags (e.g.: -analyzer-output), but some are +/// analyzer configuration options, which are preceded by -analyzer-config +/// (e.g.: -analyzer-config notes-as-events=true). +/// +/// If you'd like to add a new frontend flag, add it to +/// include/clang/Driver/CC1Options.td, add a new field to store the value of +/// that flag in this class, and initialize it in +/// lib/Frontend/CompilerInvocation.cpp. +/// +/// If you'd like to add a new non-checker configuration, register it in +/// include/clang/StaticAnalyzer/Core/AnalyzerOptions.def, and refer to the +/// top of the file for documentation. +/// +/// If you'd like to add a new checker option, call getChecker*Option() +/// whenever. +/// +/// Some of the options are controlled by raw frontend flags for no good reason, +/// and should be eventually converted into -analyzer-config flags. New analyzer +/// options should not be implemented as frontend flags. Frontend flags still +/// make sense for things that do not affect the actual analysis. class AnalyzerOptions : public RefCountedBase<AnalyzerOptions> { public: using ConfigTable = llvm::StringMap<std::string>; @@ -132,6 +171,7 @@ public: std::vector<std::pair<std::string, bool>> CheckersControlList; /// A key-value table of use-specified configuration values. + // TODO: This shouldn't be public. ConfigTable Config; AnalysisStores AnalysisStoreOpt = RegionStoreModel; AnalysisConstraints AnalysisConstraintsOpt = RangeConstraintsModel; @@ -140,6 +180,9 @@ public: std::string AnalyzeSpecificFunction; + /// File path to which the exploded graph should be dumped. + std::string DumpExplodedGraphTo; + /// Store full compiler invocation for reproducible instructions in the /// generated report. std::string FullCompilerInvocation; @@ -156,24 +199,16 @@ public: unsigned ShowCheckerHelp : 1; unsigned ShowEnabledCheckerList : 1; + unsigned ShowConfigOptionsList : 1; + unsigned ShouldEmitErrorsOnInvalidConfigValue : 1; unsigned AnalyzeAll : 1; unsigned AnalyzerDisplayProgress : 1; unsigned AnalyzeNestedBlocks : 1; - /// The flag regulates if we should eagerly assume evaluations of - /// conditionals, thus, bifurcating the path. - /// - /// This flag indicates how the engine should handle expressions such as: 'x = - /// (y != 0)'. When this flag is true then the subexpression 'y != 0' will be - /// eagerly assumed to be true or false, thus evaluating it to the integers 0 - /// or 1 respectively. The upside is that this can increase analysis - /// precision until we have a better way to lazily evaluate such logic. The - /// downside is that it eagerly bifurcates paths. unsigned eagerlyAssumeBinOpBifurcation : 1; unsigned TrimGraph : 1; unsigned visualizeExplodedGraphWithGraphViz : 1; - unsigned visualizeExplodedGraphWithUbiGraph : 1; unsigned UnoptimizedCFG : 1; unsigned PrintStats : 1; @@ -188,187 +223,51 @@ public: /// The mode of function selection used during inlining. AnalysisInliningMode InliningMode = NoRedundancy; - enum class ExplorationStrategyKind { - DFS, - BFS, - UnexploredFirst, - UnexploredFirstQueue, - BFSBlockDFSContents, - NotSet - }; - -private: - ExplorationStrategyKind ExplorationStrategy = ExplorationStrategyKind::NotSet; - - /// Describes the kinds for high-level analyzer mode. - enum UserModeKind { - UMK_NotSet = 0, - - /// Perform shallow but fast analyzes. - UMK_Shallow = 1, - - /// Perform deep analyzes. - UMK_Deep = 2 - }; - - /// Controls the high-level analyzer mode, which influences the default - /// settings for some of the lower-level config options (such as IPAMode). - /// \sa getUserMode - UserModeKind UserMode = UMK_NotSet; - - /// Controls the mode of inter-procedural analysis. - IPAKind IPAMode = IPAK_NotSet; - - /// Controls which C++ member functions will be considered for inlining. - CXXInlineableMemberKind CXXMemberInliningMode; - - /// \sa includeImplicitDtorsInCFG - Optional<bool> IncludeImplicitDtorsInCFG; - - /// \sa includeTemporaryDtorsInCFG - Optional<bool> IncludeTemporaryDtorsInCFG; - - /// \sa IncludeLifetimeInCFG - Optional<bool> IncludeLifetimeInCFG; - - /// \sa IncludeLoopExitInCFG - Optional<bool> IncludeLoopExitInCFG; - - /// \sa IncludeRichConstructorsInCFG - Optional<bool> IncludeRichConstructorsInCFG; - - /// \sa mayInlineCXXStandardLibrary - Optional<bool> InlineCXXStandardLibrary; - - /// \sa includeScopesInCFG - Optional<bool> IncludeScopesInCFG; - - /// \sa mayInlineTemplateFunctions - Optional<bool> InlineTemplateFunctions; - - /// \sa mayInlineCXXAllocator - Optional<bool> InlineCXXAllocator; - - /// \sa mayInlineCXXContainerMethods - Optional<bool> InlineCXXContainerMethods; - - /// \sa mayInlineCXXSharedPtrDtor - Optional<bool> InlineCXXSharedPtrDtor; - - /// \sa mayInlineCXXTemporaryDtors - Optional<bool> InlineCXXTemporaryDtors; + // Create a field for each -analyzer-config option. +#define ANALYZER_OPTION_DEPENDS_ON_USER_MODE(TYPE, NAME, CMDFLAG, DESC, \ + SHALLOW_VAL, DEEP_VAL) \ + ANALYZER_OPTION(TYPE, NAME, CMDFLAG, DESC, SHALLOW_VAL) - /// \sa mayInlineObjCMethod - Optional<bool> ObjCInliningMode; +#define ANALYZER_OPTION(TYPE, NAME, CMDFLAG, DESC, DEFAULT_VAL) \ + TYPE NAME; - // Cache of the "ipa-always-inline-size" setting. - // \sa getAlwaysInlineSize - Optional<unsigned> AlwaysInlineSize; +#include "clang/StaticAnalyzer/Core/AnalyzerOptions.def" +#undef ANALYZER_OPTION +#undef ANALYZER_OPTION_DEPENDS_ON_USER_MODE - /// \sa shouldSuppressNullReturnPaths - Optional<bool> SuppressNullReturnPaths; + // Create an array of all -analyzer-config command line options. Sort it in + // the constructor. + std::vector<StringRef> AnalyzerConfigCmdFlags = { +#define ANALYZER_OPTION_DEPENDS_ON_USER_MODE(TYPE, NAME, CMDFLAG, DESC, \ + SHALLOW_VAL, DEEP_VAL) \ + ANALYZER_OPTION(TYPE, NAME, CMDFLAG, DESC, SHALLOW_VAL) - // \sa getMaxInlinableSize - Optional<unsigned> MaxInlinableSize; +#define ANALYZER_OPTION(TYPE, NAME, CMDFLAG, DESC, DEFAULT_VAL) \ + CMDFLAG, - /// \sa shouldAvoidSuppressingNullArgumentPaths - Optional<bool> AvoidSuppressingNullArgumentPaths; - - /// \sa shouldSuppressInlinedDefensiveChecks - Optional<bool> SuppressInlinedDefensiveChecks; - - /// \sa shouldSuppressFromCXXStandardLibrary - Optional<bool> SuppressFromCXXStandardLibrary; - - /// \sa shouldCrosscheckWithZ3 - Optional<bool> CrosscheckWithZ3; - - /// \sa reportIssuesInMainSourceFile - Optional<bool> ReportIssuesInMainSourceFile; - - /// \sa StableReportFilename - Optional<bool> StableReportFilename; - - Optional<bool> SerializeStats; - - /// \sa getGraphTrimInterval - Optional<unsigned> GraphTrimInterval; - - /// \sa getMaxSymbolComplexity - Optional<unsigned> MaxSymbolComplexity; - - /// \sa getMaxTimesInlineLarge - Optional<unsigned> MaxTimesInlineLarge; - - /// \sa getMinCFGSizeTreatFunctionsAsLarge - Optional<unsigned> MinCFGSizeTreatFunctionsAsLarge; - - /// \sa getMaxNodesPerTopLevelFunction - Optional<unsigned> MaxNodesPerTopLevelFunction; - - /// \sa shouldInlineLambdas - Optional<bool> InlineLambdas; - - /// \sa shouldWidenLoops - Optional<bool> WidenLoops; - - /// \sa shouldUnrollLoops - Optional<bool> UnrollLoops; - - /// \sa shouldDisplayNotesAsEvents - Optional<bool> DisplayNotesAsEvents; - - /// \sa shouldAggressivelySimplifyBinaryOperation - Optional<bool> AggressiveBinaryOperationSimplification; - - /// \sa getCTUDir - Optional<StringRef> CTUDir; - - /// \sa getCTUIndexName - Optional<StringRef> CTUIndexName; - - /// \sa naiveCTUEnabled - Optional<bool> NaiveCTU; +#include "clang/StaticAnalyzer/Core/AnalyzerOptions.def" +#undef ANALYZER_OPTION +#undef ANALYZER_OPTION_DEPENDS_ON_USER_MODE + }; - /// \sa shouldElideConstructors - Optional<bool> ElideConstructors; + bool isUnknownAnalyzerConfig(StringRef Name) const { + assert(std::is_sorted(AnalyzerConfigCmdFlags.begin(), + AnalyzerConfigCmdFlags.end())); - /// A helper function that retrieves option for a given full-qualified - /// checker name. - /// Options for checkers can be specified via 'analyzer-config' command-line - /// option. - /// Example: - /// @code-analyzer-config unix.Malloc:OptionName=CheckerOptionValue @endcode - /// or @code-analyzer-config unix:OptionName=GroupOptionValue @endcode - /// for groups of checkers. - /// @param [in] CheckerName Full-qualified checker name, like - /// alpha.unix.StreamChecker. - /// @param [in] OptionName Name of the option to get. - /// @param [in] Default Default value if no option is specified. - /// @param [in] SearchInParents If set to true and the searched option was not - /// specified for the given checker the options for the parent packages will - /// be searched as well. The inner packages take precedence over the outer - /// ones. - /// @retval CheckerOptionValue An option for a checker if it was specified. - /// @retval GroupOptionValue An option for group if it was specified and no - /// checker-specific options were found. The closer group to checker, - /// the more priority it has. For example, @c coregroup.subgroup has more - /// priority than @c coregroup for @c coregroup.subgroup.CheckerName checker. - /// @retval Default If nor checker option, nor group option was found. - StringRef getCheckerOption(StringRef CheckerName, StringRef OptionName, - StringRef Default, - bool SearchInParents = false); + return !std::binary_search(AnalyzerConfigCmdFlags.begin(), + AnalyzerConfigCmdFlags.end(), Name); + } -public: AnalyzerOptions() : DisableAllChecks(false), ShowCheckerHelp(false), - ShowEnabledCheckerList(false), AnalyzeAll(false), - AnalyzerDisplayProgress(false), AnalyzeNestedBlocks(false), - eagerlyAssumeBinOpBifurcation(false), TrimGraph(false), - visualizeExplodedGraphWithGraphViz(false), - visualizeExplodedGraphWithUbiGraph(false), UnoptimizedCFG(false), - PrintStats(false), NoRetryExhausted(false), CXXMemberInliningMode() {} + ShowEnabledCheckerList(false), ShowConfigOptionsList(false), + AnalyzeAll(false), AnalyzerDisplayProgress(false), + AnalyzeNestedBlocks(false), eagerlyAssumeBinOpBifurcation(false), + TrimGraph(false), visualizeExplodedGraphWithGraphViz(false), + UnoptimizedCFG(false), PrintStats(false), NoRetryExhausted(false) { + llvm::sort(AnalyzerConfigCmdFlags); + } /// Interprets an option's string value as a boolean. The "true" string is /// interpreted as true and the "false" string is interpreted as false. @@ -377,34 +276,17 @@ public: /// @param [in] Name Name for option to retrieve. /// @param [in] DefaultVal Default value returned if no such option was /// specified. - /// @param [in] C The optional checker parameter that can be used to restrict - /// the search to the options of this particular checker (and its parents - /// depending on search mode). + /// @param [in] C The checker object the option belongs to. Checker options + /// are retrieved in the following format: + /// `-analyzer-config <package and checker name>:OptionName=Value. /// @param [in] SearchInParents If set to true and the searched option was not /// specified for the given checker the options for the parent packages will /// be searched as well. The inner packages take precedence over the outer /// ones. - bool getBooleanOption(StringRef Name, bool DefaultVal, - const ento::CheckerBase *C = nullptr, - bool SearchInParents = false); + bool getCheckerBooleanOption(StringRef Name, bool DefaultVal, + const ento::CheckerBase *C, + bool SearchInParents = false) const; - /// Variant that accepts a Optional value to cache the result. - /// - /// @param [in,out] V Return value storage, returned if parameter contains - /// an existing valid option, else it is used to store a return value - /// @param [in] Name Name for option to retrieve. - /// @param [in] DefaultVal Default value returned if no such option was - /// specified. - /// @param [in] C The optional checker parameter that can be used to restrict - /// the search to the options of this particular checker (and its parents - /// depending on search mode). - /// @param [in] SearchInParents If set to true and the searched option was not - /// specified for the given checker the options for the parent packages will - /// be searched as well. The inner packages take precedence over the outer - /// ones. - bool getBooleanOption(Optional<bool> &V, StringRef Name, bool DefaultVal, - const ento::CheckerBase *C = nullptr, - bool SearchInParents = false); /// Interprets an option's string value as an integer value. /// @@ -412,16 +294,16 @@ public: /// @param [in] Name Name for option to retrieve. /// @param [in] DefaultVal Default value returned if no such option was /// specified. - /// @param [in] C The optional checker parameter that can be used to restrict - /// the search to the options of this particular checker (and its parents - /// depending on search mode). + /// @param [in] C The checker object the option belongs to. Checker options + /// are retrieved in the following format: + /// `-analyzer-config <package and checker name>:OptionName=Value. /// @param [in] SearchInParents If set to true and the searched option was not /// specified for the given checker the options for the parent packages will /// be searched as well. The inner packages take precedence over the outer /// ones. - int getOptionAsInteger(StringRef Name, int DefaultVal, - const ento::CheckerBase *C = nullptr, - bool SearchInParents = false); + int getCheckerIntegerOption(StringRef Name, int DefaultVal, + const ento::CheckerBase *C, + bool SearchInParents = false) const; /// Query an option's string value. /// @@ -429,26 +311,26 @@ public: /// @param [in] Name Name for option to retrieve. /// @param [in] DefaultVal Default value returned if no such option was /// specified. - /// @param [in] C The optional checker parameter that can be used to restrict - /// the search to the options of this particular checker (and its parents - /// depending on search mode). + /// @param [in] C The checker object the option belongs to. Checker options + /// are retrieved in the following format: + /// `-analyzer-config <package and checker name>:OptionName=Value. /// @param [in] SearchInParents If set to true and the searched option was not /// specified for the given checker the options for the parent packages will /// be searched as well. The inner packages take precedence over the outer /// ones. - StringRef getOptionAsString(StringRef Name, StringRef DefaultVal, - const ento::CheckerBase *C = nullptr, - bool SearchInParents = false); + StringRef getCheckerStringOption(StringRef Name, StringRef DefaultVal, + const ento::CheckerBase *C, + bool SearchInParents = false) const; /// Retrieves and sets the UserMode. This is a high-level option, /// which is used to set other low-level options. It is not accessible /// outside of AnalyzerOptions. - UserModeKind getUserMode(); + UserModeKind getUserMode() const; - ExplorationStrategyKind getExplorationStrategy(); + ExplorationStrategyKind getExplorationStrategy() const; /// Returns the inter-procedural analysis mode. - IPAKind getIPAMode(); + IPAKind getIPAMode() const; /// Returns the option controlling which C++ member functions will be /// considered for inlining. @@ -456,275 +338,28 @@ public: /// This is controlled by the 'c++-inlining' config option. /// /// \sa CXXMemberInliningMode - bool mayInlineCXXMemberFunction(CXXInlineableMemberKind K); - - /// Returns true if ObjectiveC inlining is enabled, false otherwise. - bool mayInlineObjCMethod(); - - /// Returns whether or not the destructors for C++ temporary objects should - /// be included in the CFG. - /// - /// This is controlled by the 'cfg-temporary-dtors' config option, which - /// accepts the values "true" and "false". - bool includeTemporaryDtorsInCFG(); - - /// Returns whether or not implicit destructors for C++ objects should - /// be included in the CFG. - /// - /// This is controlled by the 'cfg-implicit-dtors' config option, which - /// accepts the values "true" and "false". - bool includeImplicitDtorsInCFG(); - - /// Returns whether or not end-of-lifetime information should be included in - /// the CFG. - /// - /// This is controlled by the 'cfg-lifetime' config option, which accepts - /// the values "true" and "false". - bool includeLifetimeInCFG(); - - /// Returns whether or not the end of the loop information should be included - /// in the CFG. - /// - /// This is controlled by the 'cfg-loopexit' config option, which accepts - /// the values "true" and "false". - bool includeLoopExitInCFG(); - - /// Returns whether or not construction site information should be included - /// in the CFG C++ constructor elements. - /// - /// This is controlled by the 'cfg-rich-constructors' config options, - /// which accepts the values "true" and "false". - bool includeRichConstructorsInCFG(); - - /// Returns whether or not scope information should be included in the CFG. - /// - /// This is controlled by the 'cfg-scope-info' config option, which accepts - /// the values "true" and "false". - bool includeScopesInCFG(); - - /// Returns whether or not C++ standard library functions may be considered - /// for inlining. - /// - /// This is controlled by the 'c++-stdlib-inlining' config option, which - /// accepts the values "true" and "false". - bool mayInlineCXXStandardLibrary(); - - /// Returns whether or not templated functions may be considered for inlining. - /// - /// This is controlled by the 'c++-template-inlining' config option, which - /// accepts the values "true" and "false". - bool mayInlineTemplateFunctions(); - - /// Returns whether or not allocator call may be considered for inlining. - /// - /// This is controlled by the 'c++-allocator-inlining' config option, which - /// accepts the values "true" and "false". - bool mayInlineCXXAllocator(); - - /// Returns whether or not methods of C++ container objects may be considered - /// for inlining. - /// - /// This is controlled by the 'c++-container-inlining' config option, which - /// accepts the values "true" and "false". - bool mayInlineCXXContainerMethods(); - - /// Returns whether or not the destructor of C++ 'shared_ptr' may be - /// considered for inlining. - /// - /// This covers std::shared_ptr, std::tr1::shared_ptr, and boost::shared_ptr, - /// and indeed any destructor named "~shared_ptr". - /// - /// This is controlled by the 'c++-shared_ptr-inlining' config option, which - /// accepts the values "true" and "false". - bool mayInlineCXXSharedPtrDtor(); - - /// Returns true if C++ temporary destructors should be inlined during - /// analysis. - /// - /// If temporary destructors are disabled in the CFG via the - /// 'cfg-temporary-dtors' option, temporary destructors would not be - /// inlined anyway. - /// - /// This is controlled by the 'c++-temp-dtor-inlining' config option, which - /// accepts the values "true" and "false". - bool mayInlineCXXTemporaryDtors(); - - /// Returns whether or not paths that go through null returns should be - /// suppressed. - /// - /// This is a heuristic for avoiding bug reports with paths that go through - /// inlined functions that are more defensive than their callers. - /// - /// This is controlled by the 'suppress-null-return-paths' config option, - /// which accepts the values "true" and "false". - bool shouldSuppressNullReturnPaths(); - - /// Returns whether a bug report should \em not be suppressed if its path - /// includes a call with a null argument, even if that call has a null return. - /// - /// This option has no effect when #shouldSuppressNullReturnPaths() is false. - /// - /// This is a counter-heuristic to avoid false negatives. - /// - /// This is controlled by the 'avoid-suppressing-null-argument-paths' config - /// option, which accepts the values "true" and "false". - bool shouldAvoidSuppressingNullArgumentPaths(); - - /// Returns whether or not diagnostics containing inlined defensive NULL - /// checks should be suppressed. - /// - /// This is controlled by the 'suppress-inlined-defensive-checks' config - /// option, which accepts the values "true" and "false". - bool shouldSuppressInlinedDefensiveChecks(); - - /// Returns whether or not diagnostics reported within the C++ standard - /// library should be suppressed. - /// - /// This is controlled by the 'suppress-c++-stdlib' config option, - /// which accepts the values "true" and "false". - bool shouldSuppressFromCXXStandardLibrary(); - - /// Returns whether bug reports should be crosschecked with the Z3 - /// constraint manager backend. - /// - /// This is controlled by the 'crosscheck-with-z3' config option, - /// which accepts the values "true" and "false". - bool shouldCrosscheckWithZ3(); - - /// Returns whether or not the diagnostic report should be always reported - /// in the main source file and not the headers. - /// - /// This is controlled by the 'report-in-main-source-file' config option, - /// which accepts the values "true" and "false". - bool shouldReportIssuesInMainSourceFile(); - - /// Returns whether or not the report filename should be random or not. - /// - /// This is controlled by the 'stable-report-filename' config option, - /// which accepts the values "true" and "false". Default = false - bool shouldWriteStableReportFilename(); - - /// \return Whether the analyzer should - /// serialize statistics to plist output. - /// Statistics would be serialized in JSON format inside the main dictionary - /// under the \c statistics key. - /// Available only if compiled in assert mode or with LLVM statistics - /// explicitly enabled. - bool shouldSerializeStats(); - - /// Returns whether irrelevant parts of a bug report path should be pruned - /// out of the final output. - /// - /// This is controlled by the 'prune-paths' config option, which accepts the - /// values "true" and "false". - bool shouldPrunePaths(); - - /// Returns true if 'static' initializers should be in conditional logic - /// in the CFG. - bool shouldConditionalizeStaticInitializers(); - - // Returns the size of the functions (in basic blocks), which should be - // considered to be small enough to always inline. - // - // This is controlled by "ipa-always-inline-size" analyzer-config option. - unsigned getAlwaysInlineSize(); - - // Returns the bound on the number of basic blocks in an inlined function - // (50 by default). - // - // This is controlled by "-analyzer-config max-inlinable-size" option. - unsigned getMaxInlinableSize(); - - /// Returns true if the analyzer engine should synthesize fake bodies - /// for well-known functions. - bool shouldSynthesizeBodies(); - - /// Returns how often nodes in the ExplodedGraph should be recycled to save - /// memory. - /// - /// This is controlled by the 'graph-trim-interval' config option. To disable - /// node reclamation, set the option to "0". - unsigned getGraphTrimInterval(); - - /// Returns the maximum complexity of symbolic constraint (50 by default). - /// - /// This is controlled by "-analyzer-config max-symbol-complexity" option. - unsigned getMaxSymbolComplexity(); - - /// Returns the maximum times a large function could be inlined. - /// - /// This is controlled by the 'max-times-inline-large' config option. - unsigned getMaxTimesInlineLarge(); - - /// Returns the number of basic blocks a function needs to have to be - /// considered large for the 'max-times-inline-large' config option. - /// - /// This is controlled by the 'min-cfg-size-treat-functions-as-large' config - /// option. - unsigned getMinCFGSizeTreatFunctionsAsLarge(); - - /// Returns the maximum number of nodes the analyzer can generate while - /// exploring a top level function (for each exploded graph). - /// 150000 is default; 0 means no limit. - /// - /// This is controlled by the 'max-nodes' config option. - unsigned getMaxNodesPerTopLevelFunction(); - - /// Returns true if lambdas should be inlined. Otherwise a sink node will be - /// generated each time a LambdaExpr is visited. - bool shouldInlineLambdas(); - - /// Returns true if the analysis should try to widen loops. - /// This is controlled by the 'widen-loops' config option. - bool shouldWidenLoops(); - - /// Returns true if the analysis should try to unroll loops with known bounds. - /// This is controlled by the 'unroll-loops' config option. - bool shouldUnrollLoops(); - - /// Returns true if the bug reporter should transparently treat extra note - /// diagnostic pieces as event diagnostic pieces. Useful when the diagnostic - /// consumer doesn't support the extra note pieces. - /// - /// This is controlled by the 'extra-notes-as-events' option, which defaults - /// to false when unset. - bool shouldDisplayNotesAsEvents(); - - /// Returns true if SValBuilder should rearrange comparisons and additive - /// operations of symbolic expressions which consist of a sum of a symbol and - /// a concrete integer into the format where symbols are on the left-hand - /// side and the integer is on the right. This is only done if both symbols - /// and both concrete integers are signed, greater than or equal to the - /// quarter of the minimum value of the type and less than or equal to the - /// quarter of the maximum value of that type. - /// - /// A + n <OP> B + m becomes A - B <OP> m - n, where A and B symbolic, - /// n and m are integers. <OP> is any of '==', '!=', '<', '<=', '>', '>=', - /// '+' or '-'. The rearrangement also happens with '-' instead of '+' on - // either or both side and also if any or both integers are missing. - bool shouldAggressivelySimplifyBinaryOperation(); - - /// Returns the directory containing the CTU related files. - StringRef getCTUDir(); - - /// Returns the name of the file containing the CTU index of functions. - StringRef getCTUIndexName(); - - /// Returns true when naive cross translation unit analysis is enabled. - /// This is an experimental feature to inline functions from another - /// translation units. - bool naiveCTUEnabled(); - - /// Returns true if elidable C++ copy-constructors and move-constructors - /// should be actually elided during analysis. Both behaviors are allowed - /// by the C++ standard, and the analyzer, like CodeGen, defaults to eliding. - /// Starting with C++17 some elisions become mandatory, and in these cases - /// the option will be ignored. - bool shouldElideConstructors(); + bool mayInlineCXXMemberFunction(CXXInlineableMemberKind K) const; }; using AnalyzerOptionsRef = IntrusiveRefCntPtr<AnalyzerOptions>; +//===----------------------------------------------------------------------===// +// We'll use AnalyzerOptions in the frontend, but we can't link the frontend +// with clangStaticAnalyzerCore, because clangStaticAnalyzerCore depends on +// clangFrontend. +// +// For this reason, implement some methods in this header file. +//===----------------------------------------------------------------------===// + +inline UserModeKind AnalyzerOptions::getUserMode() const { + auto K = llvm::StringSwitch<llvm::Optional<UserModeKind>>(UserMode) + .Case("shallow", UMK_Shallow) + .Case("deep", UMK_Deep) + .Default(None); + assert(K.hasValue() && "User mode is invalid."); + return K.getValue(); +} + } // namespace clang #endif // LLVM_CLANG_STATICANALYZER_CORE_ANALYZEROPTIONS_H diff --git a/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h b/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h index da019f83c214..c023ed5641a3 100644 --- a/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h +++ b/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h @@ -58,7 +58,7 @@ public: /// The last parameter can be used to register a new visitor with the given /// BugReport while processing a node. virtual std::shared_ptr<PathDiagnosticPiece> - VisitNode(const ExplodedNode *Succ, const ExplodedNode *Pred, + VisitNode(const ExplodedNode *Succ, BugReporterContext &BRC, BugReport &BR) = 0; /// Last function called on the visitor, no further calls to VisitNode @@ -83,6 +83,8 @@ public: BugReport &BR); }; +/// Finds last store into the given region, +/// which is different from a given symbolic value. class FindLastStoreBRVisitor final : public BugReporterVisitor { const MemRegion *R; SVal V; @@ -105,7 +107,6 @@ public: void Profile(llvm::FoldingSetNodeID &ID) const override; std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N, - const ExplodedNode *PrevN, BugReporterContext &BRC, BugReport &BR) override; }; @@ -132,7 +133,6 @@ public: static const char *getTag(); std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N, - const ExplodedNode *PrevN, BugReporterContext &BRC, BugReport &BR) override; @@ -151,7 +151,6 @@ public: } std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N, - const ExplodedNode *PrevN, BugReporterContext &BRC, BugReport &BR) override; @@ -177,12 +176,10 @@ public: static const char *getTag(); std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N, - const ExplodedNode *Prev, BugReporterContext &BRC, BugReport &BR) override; std::shared_ptr<PathDiagnosticPiece> VisitNodeImpl(const ExplodedNode *N, - const ExplodedNode *Prev, BugReporterContext &BRC, BugReport &BR); @@ -235,10 +232,9 @@ public: ID.AddPointer(getTag()); } - std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N, - const ExplodedNode *Prev, - BugReporterContext &BRC, - BugReport &BR) override { + std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *, + BugReporterContext &, + BugReport &) override { return nullptr; } @@ -265,7 +261,6 @@ public: } std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N, - const ExplodedNode *PrevN, BugReporterContext &BRC, BugReport &BR) override; }; @@ -295,7 +290,6 @@ public: static const char *getTag(); std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *Succ, - const ExplodedNode *Pred, BugReporterContext &BRC, BugReport &BR) override; }; @@ -309,7 +303,6 @@ public: void Profile(llvm::FoldingSetNodeID &ID) const override {} std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *Succ, - const ExplodedNode *Pred, BugReporterContext &BRC, BugReport &BR) override; }; @@ -325,7 +318,6 @@ public: void Profile(llvm::FoldingSetNodeID &ID) const override { ID.Add(V); } std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N, - const ExplodedNode *PrevN, BugReporterContext &BRC, BugReport &BR) override; }; @@ -344,7 +336,6 @@ public: void Profile(llvm::FoldingSetNodeID &ID) const override; std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N, - const ExplodedNode *PrevN, BugReporterContext &BRC, BugReport &BR) override; @@ -354,30 +345,22 @@ public: namespace bugreporter { -/// Attempts to add visitors to trace a null or undefined value back to its -/// point of origin, whether it is a symbol constrained to null or an explicit -/// assignment. +/// Attempts to add visitors to track expression value back to its point of +/// origin. /// /// \param N A node "downstream" from the evaluation of the statement. -/// \param S The statement whose value is null or undefined. +/// \param E The expression value which we are tracking /// \param R The bug report to which visitors should be attached. -/// \param IsArg Whether the statement is an argument to an inlined function. -/// If this is the case, \p N \em must be the CallEnter node for -/// the function. /// \param EnableNullFPSuppression Whether we should employ false positive /// suppression (inlined defensive checks, returned null). /// /// \return Whether or not the function was able to add visitors for this /// statement. Note that returning \c true does not actually imply /// that any visitors were added. -bool trackNullOrUndefValue(const ExplodedNode *N, const Stmt *S, BugReport &R, - bool IsArg = false, - bool EnableNullFPSuppression = true); +bool trackExpressionValue(const ExplodedNode *N, const Expr *E, BugReport &R, + bool EnableNullFPSuppression = true); const Expr *getDerefExpr(const Stmt *S); -const Stmt *GetDenomExpr(const ExplodedNode *N); -const Stmt *GetRetValExpr(const ExplodedNode *N); -bool isDeclRefExprToReference(const Expr *E); } // namespace bugreporter diff --git a/include/clang/StaticAnalyzer/Core/BugReporter/BugType.h b/include/clang/StaticAnalyzer/Core/BugReporter/BugType.h index 3c1f8f718a3b..727ec7c66a89 100644 --- a/include/clang/StaticAnalyzer/Core/BugReporter/BugType.h +++ b/include/clang/StaticAnalyzer/Core/BugReporter/BugType.h @@ -65,8 +65,6 @@ public: /// by a sink node. bool isSuppressOnSink() const { return SuppressOnSink; } void setSuppressOnSink(bool x) { SuppressOnSink = x; } - - virtual void FlushReports(BugReporter& BR); }; class BuiltinBug : public BugType { diff --git a/include/clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h b/include/clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h index 0e80e7bc19ba..d07525661a6c 100644 --- a/include/clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h +++ b/include/clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h @@ -16,7 +16,7 @@ namespace clang { namespace categories { extern const char * const CoreFoundationObjectiveC; extern const char * const LogicError; - extern const char * const MemoryCoreFoundationObjectiveC; + extern const char * const MemoryRefCount; extern const char * const MemoryError; extern const char * const UnixAPI; } diff --git a/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h b/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h index b0bb12feba20..e9c682d7986c 100644 --- a/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h +++ b/include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h @@ -118,7 +118,7 @@ public: /// Only runs visitors, no output generated. None, - /// Used for HTML and text output. + /// Used for HTML, SARIF, and text output. Minimal, /// Used for plist output, used for "arrows" generation. @@ -178,10 +178,9 @@ public: PathDiagnosticLocation() = default; /// Create a location corresponding to the given statement. - PathDiagnosticLocation(const Stmt *s, - const SourceManager &sm, + PathDiagnosticLocation(const Stmt *s, const SourceManager &sm, LocationOrAnalysisDeclContext lac) - : K(s->getLocStart().isValid() ? StmtK : SingleLocK), + : K(s->getBeginLoc().isValid() ? StmtK : SingleLocK), S(K == StmtK ? s : nullptr), SM(&sm), Loc(genLocation(SourceLocation(), lac)), Range(genRange(lac)) { assert(K == SingleLocK || S); @@ -633,7 +632,7 @@ public: } static std::shared_ptr<PathDiagnosticCallPiece> - construct(const ExplodedNode *N, const CallExitEnd &CE, + construct(const CallExitEnd &CE, const SourceManager &SM); static PathDiagnosticCallPiece *construct(PathPieces &pieces, @@ -760,7 +759,7 @@ public: }; /// File IDs mapped to sets of line numbers. -using FilesToLineNumsMap = std::map<unsigned, std::set<unsigned>>; +using FilesToLineNumsMap = std::map<FileID, std::set<unsigned>>; /// PathDiagnostic - PathDiagnostic objects represent a single path-sensitive /// diagnostic. It represents an ordered-collection of PathDiagnosticPieces, @@ -859,13 +858,13 @@ public: meta_iterator meta_end() const { return OtherDesc.end(); } void addMeta(StringRef s) { OtherDesc.push_back(s); } - using filesmap_iterator = FilesToLineNumsMap::const_iterator; - - filesmap_iterator executedLines_begin() const { - return ExecutedLines->begin(); + const FilesToLineNumsMap &getExecutedLines() const { + return *ExecutedLines; } - filesmap_iterator executedLines_end() const { return ExecutedLines->end(); } + FilesToLineNumsMap &getExecutedLines() { + return *ExecutedLines; + } PathDiagnosticLocation getLocation() const { return Loc; diff --git a/include/clang/StaticAnalyzer/Core/Checker.h b/include/clang/StaticAnalyzer/Core/Checker.h index 8484cfe4c956..786465cee855 100644 --- a/include/clang/StaticAnalyzer/Core/Checker.h +++ b/include/clang/StaticAnalyzer/Core/Checker.h @@ -558,6 +558,8 @@ struct ImplicitNullDerefEvent { // dereference might happen later (for example pointer passed to a parameter // that is marked with nonnull attribute.) bool IsDirectDereference; + + static int Tag; }; /// A helper class which wraps a boolean value set to false by default. diff --git a/include/clang/StaticAnalyzer/Core/CheckerManager.h b/include/clang/StaticAnalyzer/Core/CheckerManager.h index 7c353326be46..538ed19f7eef 100644 --- a/include/clang/StaticAnalyzer/Core/CheckerManager.h +++ b/include/clang/StaticAnalyzer/Core/CheckerManager.h @@ -115,13 +115,14 @@ enum class ObjCMessageVisitKind { }; class CheckerManager { + ASTContext &Context; const LangOptions LangOpts; AnalyzerOptions &AOptions; CheckName CurrentCheckName; public: - CheckerManager(const LangOptions &langOpts, AnalyzerOptions &AOptions) - : LangOpts(langOpts), AOptions(AOptions) {} + CheckerManager(ASTContext &Context, AnalyzerOptions &AOptions) + : Context(Context), LangOpts(Context.getLangOpts()), AOptions(AOptions) {} ~CheckerManager(); @@ -134,6 +135,7 @@ public: const LangOptions &getLangOpts() const { return LangOpts; } AnalyzerOptions &getAnalyzerOptions() { return AOptions; } + ASTContext &getASTContext() { return Context; } using CheckerRef = CheckerBase *; using CheckerTag = const void *; @@ -149,13 +151,13 @@ public: /// /// \returns a pointer to the checker object. template <typename CHECKER, typename... AT> - CHECKER *registerChecker(AT... Args) { + CHECKER *registerChecker(AT &&... Args) { CheckerTag tag = getTag<CHECKER>(); CheckerRef &ref = CheckerTags[tag]; if (ref) return static_cast<CHECKER *>(ref); // already registered. - CHECKER *checker = new CHECKER(Args...); + CHECKER *checker = new CHECKER(std::forward<AT>(Args)...); checker->Name = CurrentCheckName; CheckerDtors.push_back(CheckerDtor(checker, destruct<CHECKER>)); CHECKER::_register(checker, *this); @@ -530,19 +532,19 @@ public: template <typename EVENT> void _registerListenerForEvent(CheckEventFunc checkfn) { - EventInfo &info = Events[getTag<EVENT>()]; + EventInfo &info = Events[&EVENT::Tag]; info.Checkers.push_back(checkfn); } template <typename EVENT> void _registerDispatcherForEvent() { - EventInfo &info = Events[getTag<EVENT>()]; + EventInfo &info = Events[&EVENT::Tag]; info.HasDispatcher = true; } template <typename EVENT> void _dispatchEvent(const EVENT &event) const { - EventsTy::const_iterator I = Events.find(getTag<EVENT>()); + EventsTy::const_iterator I = Events.find(&EVENT::Tag); if (I == Events.end()) return; const EventInfo &info = I->second; diff --git a/include/clang/StaticAnalyzer/Core/CheckerOptInfo.h b/include/clang/StaticAnalyzer/Core/CheckerOptInfo.h deleted file mode 100644 index 2d13bf34cd15..000000000000 --- a/include/clang/StaticAnalyzer/Core/CheckerOptInfo.h +++ /dev/null @@ -1,44 +0,0 @@ -//===--- CheckerOptInfo.h - Specifies which checkers to use -----*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_STATICANALYZER_CORE_CHECKEROPTINFO_H -#define LLVM_CLANG_STATICANALYZER_CORE_CHECKEROPTINFO_H - -#include "clang/Basic/LLVM.h" -#include "llvm/ADT/StringRef.h" - -namespace clang { -namespace ento { - -/// Represents a request to include or exclude a checker or package from a -/// specific analysis run. -/// -/// \sa CheckerRegistry::initializeManager -class CheckerOptInfo { - StringRef Name; - bool Enable; - bool Claimed; - -public: - CheckerOptInfo(StringRef name, bool enable) - : Name(name), Enable(enable), Claimed(false) { } - - StringRef getName() const { return Name; } - bool isEnabled() const { return Enable; } - bool isDisabled() const { return !isEnabled(); } - - bool isClaimed() const { return Claimed; } - bool isUnclaimed() const { return !isClaimed(); } - void claim() { Claimed = true; } -}; - -} // end namespace ento -} // end namespace clang - -#endif diff --git a/include/clang/StaticAnalyzer/Core/CheckerRegistry.h b/include/clang/StaticAnalyzer/Core/CheckerRegistry.h deleted file mode 100644 index d580dda73488..000000000000 --- a/include/clang/StaticAnalyzer/Core/CheckerRegistry.h +++ /dev/null @@ -1,148 +0,0 @@ -//===- CheckerRegistry.h - Maintains all available checkers -----*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_STATICANALYZER_CORE_CHECKERREGISTRY_H -#define LLVM_CLANG_STATICANALYZER_CORE_CHECKERREGISTRY_H - -#include "clang/Basic/LLVM.h" -#include "clang/StaticAnalyzer/Core/CheckerManager.h" -#include "llvm/ADT/StringMap.h" -#include "llvm/ADT/StringRef.h" -#include <cstddef> -#include <vector> - -// FIXME: move this information to an HTML file in docs/. -// At the very least, a checker plugin is a dynamic library that exports -// clang_analyzerAPIVersionString. This should be defined as follows: -// -// extern "C" -// const char clang_analyzerAPIVersionString[] = -// CLANG_ANALYZER_API_VERSION_STRING; -// -// This is used to check whether the current version of the analyzer is known to -// be incompatible with a plugin. Plugins with incompatible version strings, -// or without a version string at all, will not be loaded. -// -// To add a custom checker to the analyzer, the plugin must also define the -// function clang_registerCheckers. For example: -// -// extern "C" -// void clang_registerCheckers (CheckerRegistry ®istry) { -// registry.addChecker<MainCallChecker>("example.MainCallChecker", -// "Disallows calls to functions called main"); -// } -// -// The first method argument is the full name of the checker, including its -// enclosing package. By convention, the registered name of a checker is the -// name of the associated class (the template argument). -// The second method argument is a short human-readable description of the -// checker. -// -// The clang_registerCheckers function may add any number of checkers to the -// registry. If any checkers require additional initialization, use the three- -// argument form of CheckerRegistry::addChecker. -// -// To load a checker plugin, specify the full path to the dynamic library as -// the argument to the -load option in the cc1 frontend. You can then enable -// your custom checker using the -analyzer-checker: -// -// clang -cc1 -load </path/to/plugin.dylib> -analyze -// -analyzer-checker=<example.MainCallChecker> -// -// For a complete working example, see examples/analyzer-plugin. - -#ifndef CLANG_ANALYZER_API_VERSION_STRING -// FIXME: The Clang version string is not particularly granular; -// the analyzer infrastructure can change a lot between releases. -// Unfortunately, this string has to be statically embedded in each plugin, -// so we can't just use the functions defined in Version.h. -#include "clang/Basic/Version.h" -#define CLANG_ANALYZER_API_VERSION_STRING CLANG_VERSION_STRING -#endif - -namespace clang { - -class AnalyzerOptions; -class DiagnosticsEngine; - -namespace ento { - -class CheckerOptInfo; - -/// Manages a set of available checkers for running a static analysis. -/// The checkers are organized into packages by full name, where including -/// a package will recursively include all subpackages and checkers within it. -/// For example, the checker "core.builtin.NoReturnFunctionChecker" will be -/// included if initializeManager() is called with an option of "core", -/// "core.builtin", or the full name "core.builtin.NoReturnFunctionChecker". -class CheckerRegistry { -public: - /// Initialization functions perform any necessary setup for a checker. - /// They should include a call to CheckerManager::registerChecker. - using InitializationFunction = void (*)(CheckerManager &); - - struct CheckerInfo { - InitializationFunction Initialize; - StringRef FullName; - StringRef Desc; - - CheckerInfo(InitializationFunction fn, StringRef name, StringRef desc) - : Initialize(fn), FullName(name), Desc(desc) {} - }; - - using CheckerInfoList = std::vector<CheckerInfo>; - -private: - template <typename T> - static void initializeManager(CheckerManager &mgr) { - mgr.registerChecker<T>(); - } - -public: - /// Adds a checker to the registry. Use this non-templated overload when your - /// checker requires custom initialization. - void addChecker(InitializationFunction fn, StringRef fullName, - StringRef desc); - - /// Adds a checker to the registry. Use this templated overload when your - /// checker does not require any custom initialization. - template <class T> - void addChecker(StringRef fullName, StringRef desc) { - // Avoid MSVC's Compiler Error C2276: - // http://msdn.microsoft.com/en-us/library/850cstw1(v=VS.80).aspx - addChecker(&CheckerRegistry::initializeManager<T>, fullName, desc); - } - - /// Initializes a CheckerManager by calling the initialization functions for - /// all checkers specified by the given CheckerOptInfo list. The order of this - /// list is significant; later options can be used to reverse earlier ones. - /// This can be used to exclude certain checkers in an included package. - void initializeManager(CheckerManager &mgr, - SmallVectorImpl<CheckerOptInfo> &opts) const; - - /// Check if every option corresponds to a specific checker or package. - void validateCheckerOptions(const AnalyzerOptions &opts, - DiagnosticsEngine &diags) const; - - /// Prints the name and description of all checkers in this registry. - /// This output is not intended to be machine-parseable. - void printHelp(raw_ostream &out, size_t maxNameChars = 30) const; - void printList(raw_ostream &out, - SmallVectorImpl<CheckerOptInfo> &opts) const; - -private: - mutable CheckerInfoList Checkers; - mutable llvm::StringMap<size_t> Packages; -}; - -} // namespace ento - -} // namespace clang - -#endif // LLVM_CLANG_STATICANALYZER_CORE_CHECKERREGISTRY_H diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h index 85369509efcd..50b9b566edc3 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h @@ -46,14 +46,12 @@ class AnalysisManager : public BugReporterData { public: AnalyzerOptions &options; - AnalysisManager(ASTContext &ctx,DiagnosticsEngine &diags, - const LangOptions &lang, + AnalysisManager(ASTContext &ctx, DiagnosticsEngine &diags, const PathDiagnosticConsumers &Consumers, StoreManagerCreator storemgr, ConstraintManagerCreator constraintmgr, - CheckerManager *checkerMgr, - AnalyzerOptions &Options, - CodeInjector* injector = nullptr); + CheckerManager *checkerMgr, AnalyzerOptions &Options, + CodeInjector *injector = nullptr); ~AnalysisManager() override; @@ -102,8 +100,7 @@ public: void FlushDiagnostics(); bool shouldVisualize() const { - return options.visualizeExplodedGraphWithGraphViz || - options.visualizeExplodedGraphWithUbiGraph; + return options.visualizeExplodedGraphWithGraphViz; } bool shouldInlineCall() const { diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h b/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h index b72b158194c7..1c5d4eb2de32 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h @@ -211,7 +211,8 @@ public: } const llvm::APSInt &getTruthValue(bool b, QualType T) { - return getValue(b ? 1 : 0, Ctx.getIntWidth(T), true); + return getValue(b ? 1 : 0, Ctx.getIntWidth(T), + T->isUnsignedIntegerOrEnumerationType()); } const llvm::APSInt &getTruthValue(bool b) { diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h index 9078fb94d282..81dd83fc1071 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h @@ -80,7 +80,9 @@ class CallDescription { mutable IdentifierInfo *II = nullptr; mutable bool IsLookupDone = false; - StringRef FuncName; + // The list of the qualified names used to identify the specified CallEvent, + // e.g. "{a, b}" represent the qualified names, like "a::b". + std::vector<const char *> QualifiedName; unsigned RequiredArgs; public: @@ -88,16 +90,20 @@ public: /// Constructs a CallDescription object. /// - /// @param FuncName The name of the function that will be matched. + /// @param QualifiedName The list of the name qualifiers of the function that + /// will be matched. The user is allowed to skip any of the qualifiers. + /// For example, {"std", "basic_string", "c_str"} would match both + /// std::basic_string<...>::c_str() and std::__1::basic_string<...>::c_str(). /// /// @param RequiredArgs The number of arguments that is expected to match a /// call. Omit this parameter to match every occurrence of call with a given /// name regardless the number of arguments. - CallDescription(StringRef FuncName, unsigned RequiredArgs = NoArgRequirement) - : FuncName(FuncName), RequiredArgs(RequiredArgs) {} + CallDescription(ArrayRef<const char *> QualifiedName, + unsigned RequiredArgs = NoArgRequirement) + : QualifiedName(QualifiedName), RequiredArgs(RequiredArgs) {} /// Get the name of the function that this object matches. - StringRef getFunctionName() const { return FuncName; } + StringRef getFunctionName() const { return QualifiedName.back(); } }; template<typename T = CallEvent> @@ -428,21 +434,23 @@ public: bool isArgumentConstructedDirectly(unsigned Index) const { // This assumes that the object was not yet removed from the state. return ExprEngine::getObjectUnderConstruction( - getState(), {getOriginExpr(), Index}, getCalleeStackFrame()).hasValue(); + getState(), {getOriginExpr(), Index}, getLocationContext()).hasValue(); } /// Some calls have parameter numbering mismatched from argument numbering. /// This function converts an argument index to the corresponding /// parameter index. Returns None is the argument doesn't correspond /// to any parameter variable. - Optional<unsigned> getAdjustedParameterIndex(unsigned ArgumentIndex) const { - if (dyn_cast_or_null<CXXOperatorCallExpr>(getOriginExpr()) && - dyn_cast_or_null<CXXMethodDecl>(getDecl())) { - // For member operator calls argument 0 on the expression corresponds - // to implicit this-parameter on the declaration. - return (ArgumentIndex > 0) ? Optional<unsigned>(ArgumentIndex - 1) : None; - } - return ArgumentIndex; + virtual Optional<unsigned> + getAdjustedParameterIndex(unsigned ASTArgumentIndex) const { + return ASTArgumentIndex; + } + + /// Some call event sub-classes conveniently adjust mismatching AST indices + /// to match parameter indices. This function converts an argument index + /// as understood by CallEvent to the argument index as understood by the AST. + virtual unsigned getASTArgumentIndex(unsigned CallArgumentIndex) const { + return CallArgumentIndex; } // Iterator access to formal parameters and their types. @@ -769,6 +777,20 @@ public: static bool classof(const CallEvent *CA) { return CA->getKind() == CE_CXXMemberOperator; } + + Optional<unsigned> + getAdjustedParameterIndex(unsigned ASTArgumentIndex) const override { + // For member operator calls argument 0 on the expression corresponds + // to implicit this-parameter on the declaration. + return (ASTArgumentIndex > 0) ? Optional<unsigned>(ASTArgumentIndex - 1) + : None; + } + + unsigned getASTArgumentIndex(unsigned CallArgumentIndex) const override { + // For member operator calls argument 0 on the expression corresponds + // to implicit this-parameter on the declaration. + return CallArgumentIndex + 1; + } }; /// Represents an implicit call to a C++ destructor. @@ -793,7 +815,7 @@ protected: ProgramStateRef St, const LocationContext *LCtx) : CXXInstanceCall(DD, St, LCtx) { Data = DtorDataTy(Target, IsBaseDestructor).getOpaqueValue(); - Location = Trigger->getLocEnd(); + Location = Trigger->getEndLoc(); } CXXDestructorCall(const CXXDestructorCall &Other) = default; @@ -899,15 +921,30 @@ public: return getOriginExpr()->getOperatorNew(); } + /// Number of non-placement arguments to the call. It is equal to 2 for + /// C++17 aligned operator new() calls that have alignment implicitly + /// passed as the second argument, and to 1 for other operator new() calls. + unsigned getNumImplicitArgs() const { + return getOriginExpr()->passAlignment() ? 2 : 1; + } + unsigned getNumArgs() const override { - return getOriginExpr()->getNumPlacementArgs() + 1; + return getOriginExpr()->getNumPlacementArgs() + getNumImplicitArgs(); } const Expr *getArgExpr(unsigned Index) const override { // The first argument of an allocator call is the size of the allocation. - if (Index == 0) + if (Index < getNumImplicitArgs()) return nullptr; - return getOriginExpr()->getPlacementArg(Index - 1); + return getOriginExpr()->getPlacementArg(Index - getNumImplicitArgs()); + } + + /// Number of placement arguments to the operator new() call. For example, + /// standard std::nothrow operator new and standard placement new both have + /// 1 implicit argument (size) and 1 placement argument, while regular + /// operator new() has 1 implicit argument and 0 placement arguments. + const Expr *getPlacementArgExpr(unsigned Index) const { + return getOriginExpr()->getPlacementArg(Index); } Kind getKind() const override { return CE_CXXAllocator; } @@ -1101,9 +1138,16 @@ class CallEventManager { public: CallEventManager(llvm::BumpPtrAllocator &alloc) : Alloc(alloc) {} + /// Gets an outside caller given a callee context. CallEventRef<> getCaller(const StackFrameContext *CalleeCtx, ProgramStateRef State); + /// Gets a call event for a function call, Objective-C method call, + /// or a 'new' call. + CallEventRef<> + getCall(const Stmt *S, ProgramStateRef State, + const LocationContext *LC); + CallEventRef<> getSimpleCall(const CallExpr *E, ProgramStateRef State, const LocationContext *LCtx); diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h index ce2b711a4a1b..6ee75b738465 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h @@ -21,52 +21,6 @@ namespace clang { namespace ento { - /// Declares an immutable map of type \p NameTy, suitable for placement into - /// the ProgramState. This is implementing using llvm::ImmutableMap. - /// - /// \code - /// State = State->set<Name>(K, V); - /// const Value *V = State->get<Name>(K); // Returns NULL if not in the map. - /// State = State->remove<Name>(K); - /// NameTy Map = State->get<Name>(); - /// \endcode - /// - /// The macro should not be used inside namespaces, or for traits that must - /// be accessible from more than one translation unit. - #define REGISTER_MAP_WITH_PROGRAMSTATE(Name, Key, Value) \ - REGISTER_TRAIT_WITH_PROGRAMSTATE(Name, \ - CLANG_ENTO_PROGRAMSTATE_MAP(Key, Value)) - - /// Declares an immutable set of type \p NameTy, suitable for placement into - /// the ProgramState. This is implementing using llvm::ImmutableSet. - /// - /// \code - /// State = State->add<Name>(E); - /// State = State->remove<Name>(E); - /// bool Present = State->contains<Name>(E); - /// NameTy Set = State->get<Name>(); - /// \endcode - /// - /// The macro should not be used inside namespaces, or for traits that must - /// be accessible from more than one translation unit. - #define REGISTER_SET_WITH_PROGRAMSTATE(Name, Elem) \ - REGISTER_TRAIT_WITH_PROGRAMSTATE(Name, llvm::ImmutableSet<Elem>) - - /// Declares an immutable list of type \p NameTy, suitable for placement into - /// the ProgramState. This is implementing using llvm::ImmutableList. - /// - /// \code - /// State = State->add<Name>(E); // Adds to the /end/ of the list. - /// bool Present = State->contains<Name>(E); - /// NameTy List = State->get<Name>(); - /// \endcode - /// - /// The macro should not be used inside namespaces, or for traits that must - /// be accessible from more than one translation unit. - #define REGISTER_LIST_WITH_PROGRAMSTATE(Name, Elem) \ - REGISTER_TRAIT_WITH_PROGRAMSTATE(Name, llvm::ImmutableList<Elem>) - - class CheckerContext { ExprEngine &Eng; /// The current exploded(symbolic execution) graph node. @@ -162,10 +116,6 @@ public: return getSValBuilder().getSymbolManager(); } - bool isObjCGCEnabled() const { - return Eng.isObjCGCEnabled(); - } - ProgramStateManager &getStateManager() { return Eng.getStateManager(); } diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h b/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h index 2f8ead0746ca..b0d514dc2863 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h @@ -36,10 +36,7 @@ using DynamicTypeMapImpl = template <> struct ProgramStateTrait<DynamicTypeMap> : public ProgramStatePartialTrait<DynamicTypeMapImpl> { - static void *GDMIndex() { - static int index = 0; - return &index; - } + static void *GDMIndex(); }; /// Get dynamic type information for a region. diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h index 77e35398077c..6d498031bea0 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h @@ -93,6 +93,7 @@ public: } void print(raw_ostream &Out, const char *NL, const char *Sep, + const ASTContext &Context, const LocationContext *WithLC = nullptr) const; }; diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index 4e0c02e6d65b..bf460df278aa 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -210,10 +210,14 @@ public: return const_cast<ExplodedNode*>(this)->getFirstPred(); } - const ExplodedNode *getFirstSucc() const { + ExplodedNode *getFirstSucc() { return succ_empty() ? nullptr : *(succ_begin()); } + const ExplodedNode *getFirstSucc() const { + return const_cast<ExplodedNode*>(this)->getFirstSucc(); + } + // Iterators over successor and predecessor vertices. using succ_iterator = ExplodedNode * const *; using const_succ_iterator = const ExplodedNode * const *; @@ -240,17 +244,14 @@ public: return const_cast<ExplodedNode*>(this)->succ_end(); } - // For debugging. - -public: - class Auditor { - public: - virtual ~Auditor(); - - virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0; - }; + int64_t getID(ExplodedGraph *G) const; - static void SetAuditor(Auditor* A); + /// The node is trivial if it has only one successor, only one predecessor, + /// it's predecessor has only one successor, + /// and its program state is the same as the program state of the previous + /// node. + /// Trivial nodes may be skipped while printing exploded graph. + bool isTrivial() const; private: void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); } @@ -465,39 +466,40 @@ public: // GraphTraits namespace llvm { - - template<> struct GraphTraits<clang::ento::ExplodedNode*> { + template <> struct GraphTraits<clang::ento::ExplodedGraph *> { + using GraphTy = clang::ento::ExplodedGraph *; using NodeRef = clang::ento::ExplodedNode *; using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator; - using nodes_iterator = llvm::df_iterator<NodeRef>; - - static NodeRef getEntryNode(NodeRef N) { return N; } - - static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } + using nodes_iterator = llvm::df_iterator<GraphTy>; - static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } - - static nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); } - - static nodes_iterator nodes_end(NodeRef N) { return df_end(N); } - }; - - template<> struct GraphTraits<const clang::ento::ExplodedNode*> { - using NodeRef = const clang::ento::ExplodedNode *; - using ChildIteratorType = clang::ento::ExplodedNode::const_succ_iterator; - using nodes_iterator = llvm::df_iterator<NodeRef>; + static NodeRef getEntryNode(const GraphTy G) { + return *G->roots_begin(); + } - static NodeRef getEntryNode(NodeRef N) { return N; } + static bool predecessorOfTrivial(NodeRef N) { + return N->succ_size() == 1 && N->getFirstSucc()->isTrivial(); + } - static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } + static ChildIteratorType child_begin(NodeRef N) { + if (predecessorOfTrivial(N)) + return child_begin(*N->succ_begin()); + return N->succ_begin(); + } - static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } + static ChildIteratorType child_end(NodeRef N) { + if (predecessorOfTrivial(N)) + return child_end(N->getFirstSucc()); + return N->succ_end(); + } - static nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); } + static nodes_iterator nodes_begin(const GraphTy G) { + return df_begin(G); + } - static nodes_iterator nodes_end(NodeRef N) { return df_end(N); } + static nodes_iterator nodes_end(const GraphTy G) { + return df_end(G); + } }; - } // namespace llvm #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h index 06a90fa847a6..86b776afb822 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -141,9 +141,6 @@ private: /// implicitly never returns. ObjCNoReturn ObjCNoRet; - /// Whether or not GC is enabled in this analysis. - bool ObjCGCEnabled; - /// The BugReporter associated with this engine. It is important that /// this object be placed at the very end of member variables so that its /// destructor is called before the rest of the ExprEngine is destroyed. @@ -158,7 +155,7 @@ private: public: ExprEngine(cross_tu::CrossTranslationUnitContext &CTU, AnalysisManager &mgr, - bool gcEnabled, SetOfConstDecls *VisitedCalleesIn, + SetOfConstDecls *VisitedCalleesIn, FunctionSummariesTy *FS, InliningModes HowToInlineIn); ~ExprEngine() override; @@ -201,14 +198,24 @@ public: return *currBldrCtx; } - bool isObjCGCEnabled() { return ObjCGCEnabled; } - const Stmt *getStmt() const; void GenerateAutoTransition(ExplodedNode *N); void enqueueEndOfPath(ExplodedNodeSet &S); void GenerateCallExitNode(ExplodedNode *N); + + /// Dump graph to the specified filename. + /// If filename is empty, generate a temporary one. + /// \return The filename the graph is written into. + std::string DumpGraph(bool trim = false, StringRef Filename=""); + + /// Dump the graph consisting of the given nodes to a specified filename. + /// Generate a temporary filename if it's not provided. + /// \return The filename the graph is written into. + std::string DumpGraph(ArrayRef<const ExplodedNode *> Nodes, + StringRef Filename = ""); + /// Visualize the ExplodedGraph created by executing the simulation. void ViewGraph(bool trim = false); @@ -286,7 +293,7 @@ public: /// ProcessBranch - Called by CoreEngine. Used to generate successor /// nodes by processing the 'effects' of a branch condition. - void processBranch(const Stmt *Condition, const Stmt *Term, + void processBranch(const Stmt *Condition, NodeBuilderContext& BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, @@ -345,7 +352,7 @@ public: void processCallExit(ExplodedNode *Pred) override; /// Called by CoreEngine when the analysis worklist has terminated. - void processEndWorklist(bool hasWorkRemaining) override; + void processEndWorklist() override; /// evalAssume - Callback function invoked by the ConstraintManager when /// making assumptions about state values. @@ -608,7 +615,6 @@ protected: ProgramStateRef State, const InvalidatedSymbols *Invalidated, ArrayRef<const MemRegion *> ExplicitRegions, - ArrayRef<const MemRegion *> Regions, const CallEvent *Call, RegionAndSymbolInvalidationTraits &ITraits) override; @@ -662,6 +668,11 @@ public: const EvalCallOptions &CallOpts = {}); private: + ProgramStateRef finishArgumentConstruction(ProgramStateRef State, + const CallEvent &Call); + void finishArgumentConstruction(ExplodedNodeSet &Dst, ExplodedNode *Pred, + const CallEvent &Call); + void evalLoadCommon(ExplodedNodeSet &Dst, const Expr *NodeEx, /* Eventually will be a CFGStmt */ const Expr *BoundEx, @@ -671,14 +682,13 @@ private: const ProgramPointTag *tag, QualType LoadTy); - // FIXME: 'tag' should be removed, and a LocationContext should be used - // instead. void evalLocation(ExplodedNodeSet &Dst, const Stmt *NodeEx, /* This will eventually be a CFGStmt */ const Stmt *BoundEx, ExplodedNode *Pred, - ProgramStateRef St, SVal location, - const ProgramPointTag *tag, bool isLoad); + ProgramStateRef St, + SVal location, + bool isLoad); /// Count the stack depth and determine if the call is recursive. void examineStackFrames(const Decl *D, const LocationContext *LCtx, @@ -729,10 +739,14 @@ private: /// /// If \p Result is provided, the new region will be bound to this expression /// instead of \p InitWithAdjustments. - ProgramStateRef createTemporaryRegionIfNeeded(ProgramStateRef State, - const LocationContext *LC, - const Expr *InitWithAdjustments, - const Expr *Result = nullptr); + /// + /// Returns the temporary region with adjustments into the optional + /// OutRegionWithAdjustments out-parameter if a new region was indeed needed, + /// otherwise sets it to nullptr. + ProgramStateRef createTemporaryRegionIfNeeded( + ProgramStateRef State, const LocationContext *LC, + const Expr *InitWithAdjustments, const Expr *Result = nullptr, + const SubRegion **OutRegionWithAdjustments = nullptr); /// Returns a region representing the first element of a (possibly /// multi-dimensional) array, for the purposes of element construction or @@ -818,7 +832,7 @@ struct ReplayWithoutInlining{}; template <> struct ProgramStateTrait<ReplayWithoutInlining> : public ProgramStatePartialTrait<const void*> { - static void *GDMIndex() { static int index = 0; return &index; } + static void *GDMIndex(); }; } // namespace ento diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h b/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h index 3a93aae5a9bc..3d0ff4efa1d7 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h @@ -24,6 +24,7 @@ #include "clang/AST/Expr.h" #include "clang/AST/ExprObjC.h" #include "clang/AST/Type.h" +#include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Basic/LLVM.h" #include "clang/Basic/SourceLocation.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" @@ -118,11 +119,15 @@ public: const MemRegion *getBaseRegion() const; + /// Recursively retrieve the region of the most derived class instance of + /// regions of C++ base class instances. + const MemRegion *getMostDerivedObjectRegion() const; + /// Check if the region is a subregion of the given region. /// Each region is a subregion of itself. virtual bool isSubRegionOf(const MemRegion *R) const; - const MemRegion *StripCasts(bool StripBaseCasts = true) const; + const MemRegion *StripCasts(bool StripBaseAndDerivedCasts = true) const; /// If this is a symbolic region, returns the region. Otherwise, /// goes up the base chain looking for the first symbolic base region. @@ -763,10 +768,15 @@ class SymbolicRegion : public SubRegion { SymbolicRegion(const SymbolRef s, const MemSpaceRegion *sreg) : SubRegion(sreg, SymbolicRegionKind), sym(s) { - assert(s); + // Because pointer arithmetic is represented by ElementRegion layers, + // the base symbol here should not contain any arithmetic. + assert(s && isa<SymbolData>(s)); assert(s->getType()->isAnyPointerType() || s->getType()->isReferenceType() || s->getType()->isBlockPointerType()); + + // populateWorklistFromSymbol() relies on this assertion, and needs to be + // updated if more cases are introduced. assert(isa<UnknownSpaceRegion>(sreg) || isa<HeapSpaceRegion>(sreg)); } @@ -1072,7 +1082,7 @@ public: void dump() const; }; -/// ElementRegin is used to represent both array elements and casts. +/// ElementRegion is used to represent both array elements and casts. class ElementRegion : public TypedValueRegion { friend class MemRegionManager; @@ -1176,6 +1186,47 @@ public: } }; +// CXXDerivedObjectRegion represents a derived-class object that surrounds +// a C++ object. It is identified by the derived class declaration and the +// region of its parent object. It is a bit counter-intuitive (but not otherwise +// unseen) that this region represents a larger segment of memory that its +// super-region. +class CXXDerivedObjectRegion : public TypedValueRegion { + friend class MemRegionManager; + + const CXXRecordDecl *DerivedD; + + CXXDerivedObjectRegion(const CXXRecordDecl *DerivedD, const SubRegion *SReg) + : TypedValueRegion(SReg, CXXDerivedObjectRegionKind), DerivedD(DerivedD) { + assert(DerivedD); + // In case of a concrete region, it should always be possible to model + // the base-to-derived cast by undoing a previous derived-to-base cast, + // otherwise the cast is most likely ill-formed. + assert(SReg->getSymbolicBase() && + "Should have unwrapped a base region instead!"); + } + + static void ProfileRegion(llvm::FoldingSetNodeID &ID, const CXXRecordDecl *RD, + const MemRegion *SReg); + +public: + const CXXRecordDecl *getDecl() const { return DerivedD; } + + QualType getValueType() const override; + + void dumpToStream(raw_ostream &os) const override; + + void Profile(llvm::FoldingSetNodeID &ID) const override; + + bool canPrintPrettyAsExpr() const override; + + void printPrettyAsExpr(raw_ostream &os) const override; + + static bool classof(const MemRegion *region) { + return region->getKind() == CXXDerivedObjectRegionKind; + } +}; + template<typename RegionTy> const RegionTy* MemRegion::getAs() const { if (const auto *RT = dyn_cast<RegionTy>(this)) @@ -1326,6 +1377,14 @@ public: baseReg->isVirtual()); } + /// Create a CXXDerivedObjectRegion with the given derived class for region + /// \p Super. This should not be used for casting an existing + /// CXXBaseObjectRegion back to the derived type; instead, CXXBaseObjectRegion + /// should be removed. + const CXXDerivedObjectRegion * + getCXXDerivedObjectRegion(const CXXRecordDecl *BaseClass, + const SubRegion *Super); + const FunctionCodeRegion *getFunctionCodeRegion(const NamedDecl *FD); const BlockCodeRegion *getBlockCodeRegion(const BlockDecl *BD, CanQualType locTy, diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h index b86301a03470..c3a7028d8755 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h @@ -107,6 +107,8 @@ public: ~ProgramState(); + int64_t getID() const; + /// Return the ProgramStateManager associated with this state. ProgramStateManager &getStateManager() const { return *stateMgr; @@ -346,6 +348,8 @@ public: /// a value of such type. SVal getSValAsScalarOrLoc(const MemRegion *R) const; + using region_iterator = const MemRegion **; + /// Visits the symbols reachable from the given SVal using the provided /// SymbolVisitor. /// @@ -355,24 +359,14 @@ public: /// \sa ScanReachableSymbols bool scanReachableSymbols(SVal val, SymbolVisitor& visitor) const; - /// Visits the symbols reachable from the SVals in the given range - /// using the provided SymbolVisitor. - bool scanReachableSymbols(const SVal *I, const SVal *E, - SymbolVisitor &visitor) const; - /// Visits the symbols reachable from the regions in the given /// MemRegions range using the provided SymbolVisitor. - bool scanReachableSymbols(const MemRegion * const *I, - const MemRegion * const *E, + bool scanReachableSymbols(llvm::iterator_range<region_iterator> Reachable, SymbolVisitor &visitor) const; template <typename CB> CB scanReachableSymbols(SVal val) const; - template <typename CB> CB scanReachableSymbols(const SVal *beg, - const SVal *end) const; - template <typename CB> CB - scanReachableSymbols(const MemRegion * const *beg, - const MemRegion * const *end) const; + scanReachableSymbols(llvm::iterator_range<region_iterator> Reachable) const; /// Create a new state in which the statement is marked as tainted. LLVM_NODISCARD ProgramStateRef @@ -469,8 +463,7 @@ public: const LocationContext *CurrentLC = nullptr) const; void printDOT(raw_ostream &Out, const LocationContext *CurrentLC = nullptr) const; - void printTaint(raw_ostream &Out, const char *nl = "\n", - const char *sep = "") const; + void printTaint(raw_ostream &Out, const char *nl = "\n") const; void dump() const; void dumpTaint() const; @@ -562,15 +555,15 @@ public: MemRegionManager& getRegionManager() { return svalBuilder->getRegionManager(); } - const MemRegionManager& getRegionManager() const { + const MemRegionManager &getRegionManager() const { return svalBuilder->getRegionManager(); } CallEventManager &getCallEventManager() { return *CallEventMgr; } - StoreManager& getStoreManager() { return *StoreMgr; } - ConstraintManager& getConstraintManager() { return *ConstraintMgr; } - SubEngine* getOwningEngine() { return Eng; } + StoreManager &getStoreManager() { return *StoreMgr; } + ConstraintManager &getConstraintManager() { return *ConstraintMgr; } + SubEngine &getOwningEngine() { return *Eng; } ProgramStateRef removeDeadBindings(ProgramStateRef St, const StackFrameContext *LCtx, @@ -882,17 +875,10 @@ CB ProgramState::scanReachableSymbols(SVal val) const { } template <typename CB> -CB ProgramState::scanReachableSymbols(const SVal *beg, const SVal *end) const { - CB cb(this); - scanReachableSymbols(beg, end, cb); - return cb; -} - -template <typename CB> -CB ProgramState::scanReachableSymbols(const MemRegion * const *beg, - const MemRegion * const *end) const { +CB ProgramState::scanReachableSymbols( + llvm::iterator_range<region_iterator> Reachable) const { CB cb(this); - scanReachableSymbols(beg, end, cb); + scanReachableSymbols(Reachable, cb); return cb; } diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h index 5555b292534c..64de736c7e9f 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h @@ -30,8 +30,7 @@ namespace ento { /// Declares a program state trait for type \p Type called \p Name, and /// introduce a type named \c NameTy. - /// The macro should not be used inside namespaces, or for traits that must - /// be accessible from more than one translation unit. + /// The macro should not be used inside namespaces. #define REGISTER_TRAIT_WITH_PROGRAMSTATE(Name, Type) \ namespace { \ class Name {}; \ @@ -47,6 +46,102 @@ namespace ento { } \ } + /// Declares a factory for objects of type \p Type in the program state + /// manager. The type must provide a ::Factory sub-class. Commonly used for + /// ImmutableMap, ImmutableSet, ImmutableList. The macro should not be used + /// inside namespaces. + #define REGISTER_FACTORY_WITH_PROGRAMSTATE(Type) \ + namespace clang { \ + namespace ento { \ + template <> \ + struct ProgramStateTrait<Type> \ + : public ProgramStatePartialTrait<Type> { \ + static void *GDMIndex() { static int Index; return &Index; } \ + }; \ + } \ + } + + /// Helper for registering a map trait. + /// + /// If the map type were written directly in the invocation of + /// REGISTER_TRAIT_WITH_PROGRAMSTATE, the comma in the template arguments + /// would be treated as a macro argument separator, which is wrong. + /// This allows the user to specify a map type in a way that the preprocessor + /// can deal with. + #define CLANG_ENTO_PROGRAMSTATE_MAP(Key, Value) llvm::ImmutableMap<Key, Value> + + /// Declares an immutable map of type \p NameTy, suitable for placement into + /// the ProgramState. This is implementing using llvm::ImmutableMap. + /// + /// \code + /// State = State->set<Name>(K, V); + /// const Value *V = State->get<Name>(K); // Returns NULL if not in the map. + /// State = State->remove<Name>(K); + /// NameTy Map = State->get<Name>(); + /// \endcode + /// + /// The macro should not be used inside namespaces, or for traits that must + /// be accessible from more than one translation unit. + #define REGISTER_MAP_WITH_PROGRAMSTATE(Name, Key, Value) \ + REGISTER_TRAIT_WITH_PROGRAMSTATE(Name, \ + CLANG_ENTO_PROGRAMSTATE_MAP(Key, Value)) + + /// Declares an immutable map type \p Name and registers the factory + /// for such maps in the program state, but does not add the map itself + /// to the program state. Useful for managing lifetime of maps that are used + /// as elements of other program state data structures. + #define REGISTER_MAP_FACTORY_WITH_PROGRAMSTATE(Name, Key, Value) \ + using Name = llvm::ImmutableMap<Key, Value>; \ + REGISTER_FACTORY_WITH_PROGRAMSTATE(Name) + + + /// Declares an immutable set of type \p NameTy, suitable for placement into + /// the ProgramState. This is implementing using llvm::ImmutableSet. + /// + /// \code + /// State = State->add<Name>(E); + /// State = State->remove<Name>(E); + /// bool Present = State->contains<Name>(E); + /// NameTy Set = State->get<Name>(); + /// \endcode + /// + /// The macro should not be used inside namespaces, or for traits that must + /// be accessible from more than one translation unit. + #define REGISTER_SET_WITH_PROGRAMSTATE(Name, Elem) \ + REGISTER_TRAIT_WITH_PROGRAMSTATE(Name, llvm::ImmutableSet<Elem>) + + /// Declares an immutable set type \p Name and registers the factory + /// for such sets in the program state, but does not add the set itself + /// to the program state. Useful for managing lifetime of sets that are used + /// as elements of other program state data structures. + #define REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(Name, Elem) \ + using Name = llvm::ImmutableSet<Elem>; \ + REGISTER_FACTORY_WITH_PROGRAMSTATE(Name) + + + /// Declares an immutable list type \p NameTy, suitable for placement into + /// the ProgramState. This is implementing using llvm::ImmutableList. + /// + /// \code + /// State = State->add<Name>(E); // Adds to the /end/ of the list. + /// bool Present = State->contains<Name>(E); + /// NameTy List = State->get<Name>(); + /// \endcode + /// + /// The macro should not be used inside namespaces, or for traits that must + /// be accessible from more than one translation unit. + #define REGISTER_LIST_WITH_PROGRAMSTATE(Name, Elem) \ + REGISTER_TRAIT_WITH_PROGRAMSTATE(Name, llvm::ImmutableList<Elem>) + + /// Declares an immutable list of type \p Name and registers the factory + /// for such lists in the program state, but does not add the list itself + /// to the program state. Useful for managing lifetime of lists that are used + /// as elements of other program state data structures. + #define REGISTER_LIST_FACTORY_WITH_PROGRAMSTATE(Name, Elem) \ + using Name = llvm::ImmutableList<Elem>; \ + REGISTER_FACTORY_WITH_PROGRAMSTATE(Name) + + // Partial-specialization for ImmutableMap. template <typename Key, typename Data, typename Info> struct ProgramStatePartialTrait<llvm::ImmutableMap<Key, Data, Info>> { @@ -95,15 +190,6 @@ namespace ento { } }; - /// Helper for registering a map trait. - /// - /// If the map type were written directly in the invocation of - /// REGISTER_TRAIT_WITH_PROGRAMSTATE, the comma in the template arguments - /// would be treated as a macro argument separator, which is wrong. - /// This allows the user to specify a map type in a way that the preprocessor - /// can deal with. - #define CLANG_ENTO_PROGRAMSTATE_MAP(Key, Value) llvm::ImmutableMap<Key, Value> - // Partial-specialization for ImmutableSet. template <typename Key, typename Info> struct ProgramStatePartialTrait<llvm::ImmutableSet<Key, Info>> { diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h index d2ba1f7c9529..1b12a4edc205 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h @@ -131,7 +131,7 @@ using ConstraintRangeTy = llvm::ImmutableMap<SymbolRef, RangeSet>; template <> struct ProgramStateTrait<ConstraintRange> : public ProgramStatePartialTrait<ConstraintRangeTy> { - static void *GDMIndex() { static int Index; return &Index; } + static void *GDMIndex(); }; diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Regions.def b/include/clang/StaticAnalyzer/Core/PathSensitive/Regions.def index c84a1ff13f8b..10f89ecc55a5 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/Regions.def +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Regions.def @@ -68,6 +68,7 @@ ABSTRACT_REGION(SubRegion, MemRegion) ABSTRACT_REGION(TypedValueRegion, TypedRegion) REGION(CompoundLiteralRegion, TypedValueRegion) REGION(CXXBaseObjectRegion, TypedValueRegion) + REGION(CXXDerivedObjectRegion, TypedValueRegion) REGION(CXXTempObjectRegion, TypedValueRegion) REGION(CXXThisRegion, TypedValueRegion) ABSTRACT_REGION(DeclRegion, TypedValueRegion) diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConstraintManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConstraintManager.h index 19d3d5973e0f..8eaa9365be1d 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConstraintManager.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConstraintManager.h @@ -16,11 +16,12 @@ #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SMTCONSTRAINTMANAGER_H #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/SMTSolver.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SMTConv.h" namespace clang { namespace ento { +template <typename ConstraintSMT, typename SMTExprTy> class SMTConstraintManager : public clang::ento::SimpleConstraintManager { SMTSolverRef &Solver; @@ -34,25 +35,234 @@ public: // Implementation for interface from SimpleConstraintManager. //===------------------------------------------------------------------===// - ProgramStateRef assumeSym(ProgramStateRef state, SymbolRef Sym, - bool Assumption) override; + ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym, + bool Assumption) override { + ASTContext &Ctx = getBasicVals().getContext(); + + QualType RetTy; + bool hasComparison; + + SMTExprRef Exp = SMTConv::getExpr(Solver, Ctx, Sym, &RetTy, &hasComparison); + + // Create zero comparison for implicit boolean cast, with reversed + // assumption + if (!hasComparison && !RetTy->isBooleanType()) + return assumeExpr( + State, Sym, + SMTConv::getZeroExpr(Solver, Ctx, Exp, RetTy, !Assumption)); + + return assumeExpr(State, Sym, Assumption ? Exp : Solver->mkNot(Exp)); + } ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, - bool InRange) override; + bool InRange) override { + ASTContext &Ctx = getBasicVals().getContext(); + return assumeExpr( + State, Sym, SMTConv::getRangeExpr(Solver, Ctx, Sym, From, To, InRange)); + } ProgramStateRef assumeSymUnsupported(ProgramStateRef State, SymbolRef Sym, - bool Assumption) override; + bool Assumption) override { + // Skip anything that is unsupported + return State; + } //===------------------------------------------------------------------===// // Implementation for interface from ConstraintManager. //===------------------------------------------------------------------===// - ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override; + ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override { + ASTContext &Ctx = getBasicVals().getContext(); + + QualType RetTy; + // The expression may be casted, so we cannot call getZ3DataExpr() directly + SMTExprRef VarExp = SMTConv::getExpr(Solver, Ctx, Sym, &RetTy); + SMTExprRef Exp = + SMTConv::getZeroExpr(Solver, Ctx, VarExp, RetTy, /*Assumption=*/true); + + // Negate the constraint + SMTExprRef NotExp = + SMTConv::getZeroExpr(Solver, Ctx, VarExp, RetTy, /*Assumption=*/false); + + ConditionTruthVal isSat = checkModel(State, Sym, Exp); + ConditionTruthVal isNotSat = checkModel(State, Sym, NotExp); + + // Zero is the only possible solution + if (isSat.isConstrainedTrue() && isNotSat.isConstrainedFalse()) + return true; + + // Zero is not a solution + if (isSat.isConstrainedFalse() && isNotSat.isConstrainedTrue()) + return false; + + // Zero may be a solution + return ConditionTruthVal(); + } const llvm::APSInt *getSymVal(ProgramStateRef State, - SymbolRef Sym) const override; + SymbolRef Sym) const override { + BasicValueFactory &BVF = getBasicVals(); + ASTContext &Ctx = BVF.getContext(); + + if (const SymbolData *SD = dyn_cast<SymbolData>(Sym)) { + QualType Ty = Sym->getType(); + assert(!Ty->isRealFloatingType()); + llvm::APSInt Value(Ctx.getTypeSize(Ty), + !Ty->isSignedIntegerOrEnumerationType()); + + // TODO: this should call checkModel so we can use the cache, however, + // this method tries to get the interpretation (the actual value) from + // the solver, which is currently not cached. + + SMTExprRef Exp = + SMTConv::fromData(Solver, SD->getSymbolID(), Ty, Ctx.getTypeSize(Ty)); + + Solver->reset(); + addStateConstraints(State); + + // Constraints are unsatisfiable + Optional<bool> isSat = Solver->check(); + if (!isSat.hasValue() || !isSat.getValue()) + return nullptr; + + // Model does not assign interpretation + if (!Solver->getInterpretation(Exp, Value)) + return nullptr; + + // A value has been obtained, check if it is the only value + SMTExprRef NotExp = SMTConv::fromBinOp( + Solver, Exp, BO_NE, + Ty->isBooleanType() ? Solver->mkBoolean(Value.getBoolValue()) + : Solver->mkBitvector(Value, Value.getBitWidth()), + /*isSigned=*/false); + + Solver->addConstraint(NotExp); + + Optional<bool> isNotSat = Solver->check(); + if (!isSat.hasValue() || isNotSat.getValue()) + return nullptr; + + // This is the only solution, store it + return &BVF.getValue(Value); + } + + if (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym)) { + SymbolRef CastSym = SC->getOperand(); + QualType CastTy = SC->getType(); + // Skip the void type + if (CastTy->isVoidType()) + return nullptr; + + const llvm::APSInt *Value; + if (!(Value = getSymVal(State, CastSym))) + return nullptr; + return &BVF.Convert(SC->getType(), *Value); + } + + if (const BinarySymExpr *BSE = dyn_cast<BinarySymExpr>(Sym)) { + const llvm::APSInt *LHS, *RHS; + if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(BSE)) { + LHS = getSymVal(State, SIE->getLHS()); + RHS = &SIE->getRHS(); + } else if (const IntSymExpr *ISE = dyn_cast<IntSymExpr>(BSE)) { + LHS = &ISE->getLHS(); + RHS = getSymVal(State, ISE->getRHS()); + } else if (const SymSymExpr *SSM = dyn_cast<SymSymExpr>(BSE)) { + // Early termination to avoid expensive call + LHS = getSymVal(State, SSM->getLHS()); + RHS = LHS ? getSymVal(State, SSM->getRHS()) : nullptr; + } else { + llvm_unreachable("Unsupported binary expression to get symbol value!"); + } + + if (!LHS || !RHS) + return nullptr; + + llvm::APSInt ConvertedLHS, ConvertedRHS; + QualType LTy, RTy; + std::tie(ConvertedLHS, LTy) = SMTConv::fixAPSInt(Ctx, *LHS); + std::tie(ConvertedRHS, RTy) = SMTConv::fixAPSInt(Ctx, *RHS); + SMTConv::doIntTypeConversion<llvm::APSInt, &SMTConv::castAPSInt>( + Solver, Ctx, ConvertedLHS, LTy, ConvertedRHS, RTy); + return BVF.evalAPSInt(BSE->getOpcode(), ConvertedLHS, ConvertedRHS); + } + + llvm_unreachable("Unsupported expression to get symbol value!"); + } + + ProgramStateRef removeDeadBindings(ProgramStateRef State, + SymbolReaper &SymReaper) override { + auto CZ = State->get<ConstraintSMT>(); + auto &CZFactory = State->get_context<ConstraintSMT>(); + + for (auto I = CZ.begin(), E = CZ.end(); I != E; ++I) { + if (SymReaper.isDead(I->first)) + CZ = CZFactory.remove(CZ, *I); + } + + return State->set<ConstraintSMT>(CZ); + } + + void print(ProgramStateRef St, raw_ostream &OS, const char *nl, + const char *sep) override { + + auto CZ = St->get<ConstraintSMT>(); + + OS << nl << sep << "Constraints:"; + for (auto I = CZ.begin(), E = CZ.end(); I != E; ++I) { + OS << nl << ' ' << I->first << " : "; + I->second.print(OS); + } + OS << nl; + } + + bool canReasonAbout(SVal X) const override { + const TargetInfo &TI = getBasicVals().getContext().getTargetInfo(); + + Optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>(); + if (!SymVal) + return true; + + const SymExpr *Sym = SymVal->getSymbol(); + QualType Ty = Sym->getType(); + + // Complex types are not modeled + if (Ty->isComplexType() || Ty->isComplexIntegerType()) + return false; + + // Non-IEEE 754 floating-point types are not modeled + if ((Ty->isSpecificBuiltinType(BuiltinType::LongDouble) && + (&TI.getLongDoubleFormat() == &llvm::APFloat::x87DoubleExtended() || + &TI.getLongDoubleFormat() == &llvm::APFloat::PPCDoubleDouble()))) + return false; + + if (Ty->isRealFloatingType()) + return Solver->isFPSupported(); + + if (isa<SymbolData>(Sym)) + return true; + + SValBuilder &SVB = getSValBuilder(); + + if (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym)) + return canReasonAbout(SVB.makeSymbolVal(SC->getOperand())); + + if (const BinarySymExpr *BSE = dyn_cast<BinarySymExpr>(Sym)) { + if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(BSE)) + return canReasonAbout(SVB.makeSymbolVal(SIE->getLHS())); + + if (const IntSymExpr *ISE = dyn_cast<IntSymExpr>(BSE)) + return canReasonAbout(SVB.makeSymbolVal(ISE->getRHS())); + + if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(BSE)) + return canReasonAbout(SVB.makeSymbolVal(SSE->getLHS())) && + canReasonAbout(SVB.makeSymbolVal(SSE->getRHS())); + } + + llvm_unreachable("Unsupported expression to reason about!"); + } /// Dumps SMT formula LLVM_DUMP_METHOD void dump() const { Solver->dump(); } @@ -60,15 +270,64 @@ public: protected: // Check whether a new model is satisfiable, and update the program state. virtual ProgramStateRef assumeExpr(ProgramStateRef State, SymbolRef Sym, - const SMTExprRef &Exp) = 0; + const SMTExprRef &Exp) { + // Check the model, avoid simplifying AST to save time + if (checkModel(State, Sym, Exp).isConstrainedTrue()) + return State->add<ConstraintSMT>( + std::make_pair(Sym, static_cast<const SMTExprTy &>(*Exp))); + + return nullptr; + } /// Given a program state, construct the logical conjunction and add it to /// the solver - virtual void addStateConstraints(ProgramStateRef State) const = 0; + virtual void addStateConstraints(ProgramStateRef State) const { + // TODO: Don't add all the constraints, only the relevant ones + auto CZ = State->get<ConstraintSMT>(); + auto I = CZ.begin(), IE = CZ.end(); + + // Construct the logical AND of all the constraints + if (I != IE) { + std::vector<SMTExprRef> ASTs; + + SMTExprRef Constraint = Solver->newExprRef(I++->second); + while (I != IE) { + Constraint = Solver->mkAnd(Constraint, Solver->newExprRef(I++->second)); + } + + Solver->addConstraint(Constraint); + } + } // Generate and check a Z3 model, using the given constraint. - ConditionTruthVal checkModel(ProgramStateRef State, - const SMTExprRef &Exp) const; + ConditionTruthVal checkModel(ProgramStateRef State, SymbolRef Sym, + const SMTExprRef &Exp) const { + ProgramStateRef NewState = State->add<ConstraintSMT>( + std::make_pair(Sym, static_cast<const SMTExprTy &>(*Exp))); + + llvm::FoldingSetNodeID ID; + NewState->get<ConstraintSMT>().Profile(ID); + + unsigned hash = ID.ComputeHash(); + auto I = Cached.find(hash); + if (I != Cached.end()) + return I->second; + + Solver->reset(); + addStateConstraints(NewState); + + Optional<bool> res = Solver->check(); + if (!res.hasValue()) + Cached[hash] = ConditionTruthVal(); + else + Cached[hash] = ConditionTruthVal(res.getValue()); + + return Cached[hash]; + } + + // Cache the result of an SMT query (true, false, unknown). The key is the + // hash of the constraints in a state + mutable llvm::DenseMap<unsigned, ConditionTruthVal> Cached; }; // end class SMTConstraintManager } // namespace ento diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SMTContext.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SMTContext.h deleted file mode 100644 index 45c9df4ef401..000000000000 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SMTContext.h +++ /dev/null @@ -1,31 +0,0 @@ -//== SMTContext.h -----------------------------------------------*- C++ -*--==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines a SMT generic Context API, which will be the base class -// for every SMT solver context specific class. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SMTCONTEXT_H -#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SMTCONTEXT_H - -namespace clang { -namespace ento { - -/// Generic base class for SMT contexts -class SMTContext { -public: - SMTContext() = default; - virtual ~SMTContext() = default; -}; - -} // namespace ento -} // namespace clang - -#endif diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConv.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConv.h new file mode 100644 index 000000000000..cdca2a09700d --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SMTConv.h @@ -0,0 +1,753 @@ +//== SMTConv.h --------------------------------------------------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines a set of functions to create SMT expressions +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SMTCONV_H +#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SMTCONV_H + +#include "clang/AST/Expr.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SMTSolver.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" + +namespace clang { +namespace ento { + +class SMTConv { +public: + // Returns an appropriate sort, given a QualType and it's bit width. + static inline SMTSortRef mkSort(SMTSolverRef &Solver, const QualType &Ty, + unsigned BitWidth) { + if (Ty->isBooleanType()) + return Solver->getBoolSort(); + + if (Ty->isRealFloatingType()) + return Solver->getFloatSort(BitWidth); + + return Solver->getBitvectorSort(BitWidth); + } + + /// Constructs an SMTExprRef from an unary operator. + static inline SMTExprRef fromUnOp(SMTSolverRef &Solver, + const UnaryOperator::Opcode Op, + const SMTExprRef &Exp) { + switch (Op) { + case UO_Minus: + return Solver->mkBVNeg(Exp); + + case UO_Not: + return Solver->mkBVNot(Exp); + + case UO_LNot: + return Solver->mkNot(Exp); + + default:; + } + llvm_unreachable("Unimplemented opcode"); + } + + /// Constructs an SMTExprRef from a floating-point unary operator. + static inline SMTExprRef fromFloatUnOp(SMTSolverRef &Solver, + const UnaryOperator::Opcode Op, + const SMTExprRef &Exp) { + switch (Op) { + case UO_Minus: + return Solver->mkFPNeg(Exp); + + case UO_LNot: + return fromUnOp(Solver, Op, Exp); + + default:; + } + llvm_unreachable("Unimplemented opcode"); + } + + /// Construct an SMTExprRef from a n-ary binary operator. + static inline SMTExprRef fromNBinOp(SMTSolverRef &Solver, + const BinaryOperator::Opcode Op, + const std::vector<SMTExprRef> &ASTs) { + assert(!ASTs.empty()); + + if (Op != BO_LAnd && Op != BO_LOr) + llvm_unreachable("Unimplemented opcode"); + + SMTExprRef res = ASTs.front(); + for (std::size_t i = 1; i < ASTs.size(); ++i) + res = (Op == BO_LAnd) ? Solver->mkAnd(res, ASTs[i]) + : Solver->mkOr(res, ASTs[i]); + return res; + } + + /// Construct an SMTExprRef from a binary operator. + static inline SMTExprRef fromBinOp(SMTSolverRef &Solver, + const SMTExprRef &LHS, + const BinaryOperator::Opcode Op, + const SMTExprRef &RHS, bool isSigned) { + assert(*Solver->getSort(LHS) == *Solver->getSort(RHS) && + "AST's must have the same sort!"); + + switch (Op) { + // Multiplicative operators + case BO_Mul: + return Solver->mkBVMul(LHS, RHS); + + case BO_Div: + return isSigned ? Solver->mkBVSDiv(LHS, RHS) : Solver->mkBVUDiv(LHS, RHS); + + case BO_Rem: + return isSigned ? Solver->mkBVSRem(LHS, RHS) : Solver->mkBVURem(LHS, RHS); + + // Additive operators + case BO_Add: + return Solver->mkBVAdd(LHS, RHS); + + case BO_Sub: + return Solver->mkBVSub(LHS, RHS); + + // Bitwise shift operators + case BO_Shl: + return Solver->mkBVShl(LHS, RHS); + + case BO_Shr: + return isSigned ? Solver->mkBVAshr(LHS, RHS) : Solver->mkBVLshr(LHS, RHS); + + // Relational operators + case BO_LT: + return isSigned ? Solver->mkBVSlt(LHS, RHS) : Solver->mkBVUlt(LHS, RHS); + + case BO_GT: + return isSigned ? Solver->mkBVSgt(LHS, RHS) : Solver->mkBVUgt(LHS, RHS); + + case BO_LE: + return isSigned ? Solver->mkBVSle(LHS, RHS) : Solver->mkBVUle(LHS, RHS); + + case BO_GE: + return isSigned ? Solver->mkBVSge(LHS, RHS) : Solver->mkBVUge(LHS, RHS); + + // Equality operators + case BO_EQ: + return Solver->mkEqual(LHS, RHS); + + case BO_NE: + return fromUnOp(Solver, UO_LNot, + fromBinOp(Solver, LHS, BO_EQ, RHS, isSigned)); + + // Bitwise operators + case BO_And: + return Solver->mkBVAnd(LHS, RHS); + + case BO_Xor: + return Solver->mkBVXor(LHS, RHS); + + case BO_Or: + return Solver->mkBVOr(LHS, RHS); + + // Logical operators + case BO_LAnd: + return Solver->mkAnd(LHS, RHS); + + case BO_LOr: + return Solver->mkOr(LHS, RHS); + + default:; + } + llvm_unreachable("Unimplemented opcode"); + } + + /// Construct an SMTExprRef from a special floating-point binary operator. + static inline SMTExprRef + fromFloatSpecialBinOp(SMTSolverRef &Solver, const SMTExprRef &LHS, + const BinaryOperator::Opcode Op, + const llvm::APFloat::fltCategory &RHS) { + switch (Op) { + // Equality operators + case BO_EQ: + switch (RHS) { + case llvm::APFloat::fcInfinity: + return Solver->mkFPIsInfinite(LHS); + + case llvm::APFloat::fcNaN: + return Solver->mkFPIsNaN(LHS); + + case llvm::APFloat::fcNormal: + return Solver->mkFPIsNormal(LHS); + + case llvm::APFloat::fcZero: + return Solver->mkFPIsZero(LHS); + } + break; + + case BO_NE: + return fromFloatUnOp(Solver, UO_LNot, + fromFloatSpecialBinOp(Solver, LHS, BO_EQ, RHS)); + + default:; + } + + llvm_unreachable("Unimplemented opcode"); + } + + /// Construct an SMTExprRef from a floating-point binary operator. + static inline SMTExprRef fromFloatBinOp(SMTSolverRef &Solver, + const SMTExprRef &LHS, + const BinaryOperator::Opcode Op, + const SMTExprRef &RHS) { + assert(*Solver->getSort(LHS) == *Solver->getSort(RHS) && + "AST's must have the same sort!"); + + switch (Op) { + // Multiplicative operators + case BO_Mul: + return Solver->mkFPMul(LHS, RHS); + + case BO_Div: + return Solver->mkFPDiv(LHS, RHS); + + case BO_Rem: + return Solver->mkFPRem(LHS, RHS); + + // Additive operators + case BO_Add: + return Solver->mkFPAdd(LHS, RHS); + + case BO_Sub: + return Solver->mkFPSub(LHS, RHS); + + // Relational operators + case BO_LT: + return Solver->mkFPLt(LHS, RHS); + + case BO_GT: + return Solver->mkFPGt(LHS, RHS); + + case BO_LE: + return Solver->mkFPLe(LHS, RHS); + + case BO_GE: + return Solver->mkFPGe(LHS, RHS); + + // Equality operators + case BO_EQ: + return Solver->mkFPEqual(LHS, RHS); + + case BO_NE: + return fromFloatUnOp(Solver, UO_LNot, + fromFloatBinOp(Solver, LHS, BO_EQ, RHS)); + + // Logical operators + case BO_LAnd: + case BO_LOr: + return fromBinOp(Solver, LHS, Op, RHS, /*isSigned=*/false); + + default:; + } + + llvm_unreachable("Unimplemented opcode"); + } + + /// Construct an SMTExprRef from a QualType FromTy to a QualType ToTy, and + /// their bit widths. + static inline SMTExprRef fromCast(SMTSolverRef &Solver, const SMTExprRef &Exp, + QualType ToTy, uint64_t ToBitWidth, + QualType FromTy, uint64_t FromBitWidth) { + if ((FromTy->isIntegralOrEnumerationType() && + ToTy->isIntegralOrEnumerationType()) || + (FromTy->isAnyPointerType() ^ ToTy->isAnyPointerType()) || + (FromTy->isBlockPointerType() ^ ToTy->isBlockPointerType()) || + (FromTy->isReferenceType() ^ ToTy->isReferenceType())) { + + if (FromTy->isBooleanType()) { + assert(ToBitWidth > 0 && "BitWidth must be positive!"); + return Solver->mkIte( + Exp, Solver->mkBitvector(llvm::APSInt("1"), ToBitWidth), + Solver->mkBitvector(llvm::APSInt("0"), ToBitWidth)); + } + + if (ToBitWidth > FromBitWidth) + return FromTy->isSignedIntegerOrEnumerationType() + ? Solver->mkBVSignExt(ToBitWidth - FromBitWidth, Exp) + : Solver->mkBVZeroExt(ToBitWidth - FromBitWidth, Exp); + + if (ToBitWidth < FromBitWidth) + return Solver->mkBVExtract(ToBitWidth - 1, 0, Exp); + + // Both are bitvectors with the same width, ignore the type cast + return Exp; + } + + if (FromTy->isRealFloatingType() && ToTy->isRealFloatingType()) { + if (ToBitWidth != FromBitWidth) + return Solver->mkFPtoFP(Exp, Solver->getFloatSort(ToBitWidth)); + + return Exp; + } + + if (FromTy->isIntegralOrEnumerationType() && ToTy->isRealFloatingType()) { + SMTSortRef Sort = Solver->getFloatSort(ToBitWidth); + return FromTy->isSignedIntegerOrEnumerationType() + ? Solver->mkSBVtoFP(Exp, Sort) + : Solver->mkUBVtoFP(Exp, Sort); + } + + if (FromTy->isRealFloatingType() && ToTy->isIntegralOrEnumerationType()) + return ToTy->isSignedIntegerOrEnumerationType() + ? Solver->mkFPtoSBV(Exp, ToBitWidth) + : Solver->mkFPtoUBV(Exp, ToBitWidth); + + llvm_unreachable("Unsupported explicit type cast!"); + } + + // Callback function for doCast parameter on APSInt type. + static inline llvm::APSInt castAPSInt(SMTSolverRef &Solver, + const llvm::APSInt &V, QualType ToTy, + uint64_t ToWidth, QualType FromTy, + uint64_t FromWidth) { + APSIntType TargetType(ToWidth, !ToTy->isSignedIntegerOrEnumerationType()); + return TargetType.convert(V); + } + + /// Construct an SMTExprRef from a SymbolData. + static inline SMTExprRef fromData(SMTSolverRef &Solver, const SymbolID ID, + const QualType &Ty, uint64_t BitWidth) { + llvm::Twine Name = "$" + llvm::Twine(ID); + return Solver->mkSymbol(Name.str().c_str(), mkSort(Solver, Ty, BitWidth)); + } + + // Wrapper to generate SMTExprRef from SymbolCast data. + static inline SMTExprRef getCastExpr(SMTSolverRef &Solver, ASTContext &Ctx, + const SMTExprRef &Exp, QualType FromTy, + QualType ToTy) { + return fromCast(Solver, Exp, ToTy, Ctx.getTypeSize(ToTy), FromTy, + Ctx.getTypeSize(FromTy)); + } + + // Wrapper to generate SMTExprRef from unpacked binary symbolic expression. + // Sets the RetTy parameter. See getSMTExprRef(). + static inline SMTExprRef getBinExpr(SMTSolverRef &Solver, ASTContext &Ctx, + const SMTExprRef &LHS, QualType LTy, + BinaryOperator::Opcode Op, + const SMTExprRef &RHS, QualType RTy, + QualType *RetTy) { + SMTExprRef NewLHS = LHS; + SMTExprRef NewRHS = RHS; + doTypeConversion(Solver, Ctx, NewLHS, NewRHS, LTy, RTy); + + // Update the return type parameter if the output type has changed. + if (RetTy) { + // A boolean result can be represented as an integer type in C/C++, but at + // this point we only care about the SMT sorts. Set it as a boolean type + // to avoid subsequent SMT errors. + if (BinaryOperator::isComparisonOp(Op) || + BinaryOperator::isLogicalOp(Op)) { + *RetTy = Ctx.BoolTy; + } else { + *RetTy = LTy; + } + + // If the two operands are pointers and the operation is a subtraction, + // the result is of type ptrdiff_t, which is signed + if (LTy->isAnyPointerType() && RTy->isAnyPointerType() && Op == BO_Sub) { + *RetTy = Ctx.getPointerDiffType(); + } + } + + return LTy->isRealFloatingType() + ? fromFloatBinOp(Solver, NewLHS, Op, NewRHS) + : fromBinOp(Solver, NewLHS, Op, NewRHS, + LTy->isSignedIntegerOrEnumerationType()); + } + + // Wrapper to generate SMTExprRef from BinarySymExpr. + // Sets the hasComparison and RetTy parameters. See getSMTExprRef(). + static inline SMTExprRef getSymBinExpr(SMTSolverRef &Solver, ASTContext &Ctx, + const BinarySymExpr *BSE, + bool *hasComparison, QualType *RetTy) { + QualType LTy, RTy; + BinaryOperator::Opcode Op = BSE->getOpcode(); + + if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(BSE)) { + SMTExprRef LHS = + getSymExpr(Solver, Ctx, SIE->getLHS(), <y, hasComparison); + llvm::APSInt NewRInt; + std::tie(NewRInt, RTy) = fixAPSInt(Ctx, SIE->getRHS()); + SMTExprRef RHS = Solver->mkBitvector(NewRInt, NewRInt.getBitWidth()); + return getBinExpr(Solver, Ctx, LHS, LTy, Op, RHS, RTy, RetTy); + } + + if (const IntSymExpr *ISE = dyn_cast<IntSymExpr>(BSE)) { + llvm::APSInt NewLInt; + std::tie(NewLInt, LTy) = fixAPSInt(Ctx, ISE->getLHS()); + SMTExprRef LHS = Solver->mkBitvector(NewLInt, NewLInt.getBitWidth()); + SMTExprRef RHS = + getSymExpr(Solver, Ctx, ISE->getRHS(), &RTy, hasComparison); + return getBinExpr(Solver, Ctx, LHS, LTy, Op, RHS, RTy, RetTy); + } + + if (const SymSymExpr *SSM = dyn_cast<SymSymExpr>(BSE)) { + SMTExprRef LHS = + getSymExpr(Solver, Ctx, SSM->getLHS(), <y, hasComparison); + SMTExprRef RHS = + getSymExpr(Solver, Ctx, SSM->getRHS(), &RTy, hasComparison); + return getBinExpr(Solver, Ctx, LHS, LTy, Op, RHS, RTy, RetTy); + } + + llvm_unreachable("Unsupported BinarySymExpr type!"); + } + + // Recursive implementation to unpack and generate symbolic expression. + // Sets the hasComparison and RetTy parameters. See getExpr(). + static inline SMTExprRef getSymExpr(SMTSolverRef &Solver, ASTContext &Ctx, + SymbolRef Sym, QualType *RetTy, + bool *hasComparison) { + if (const SymbolData *SD = dyn_cast<SymbolData>(Sym)) { + if (RetTy) + *RetTy = Sym->getType(); + + return fromData(Solver, SD->getSymbolID(), Sym->getType(), + Ctx.getTypeSize(Sym->getType())); + } + + if (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym)) { + if (RetTy) + *RetTy = Sym->getType(); + + QualType FromTy; + SMTExprRef Exp = + getSymExpr(Solver, Ctx, SC->getOperand(), &FromTy, hasComparison); + + // Casting an expression with a comparison invalidates it. Note that this + // must occur after the recursive call above. + // e.g. (signed char) (x > 0) + if (hasComparison) + *hasComparison = false; + return getCastExpr(Solver, Ctx, Exp, FromTy, Sym->getType()); + } + + if (const BinarySymExpr *BSE = dyn_cast<BinarySymExpr>(Sym)) { + SMTExprRef Exp = getSymBinExpr(Solver, Ctx, BSE, hasComparison, RetTy); + // Set the hasComparison parameter, in post-order traversal order. + if (hasComparison) + *hasComparison = BinaryOperator::isComparisonOp(BSE->getOpcode()); + return Exp; + } + + llvm_unreachable("Unsupported SymbolRef type!"); + } + + // Generate an SMTExprRef that represents the given symbolic expression. + // Sets the hasComparison parameter if the expression has a comparison + // operator. Sets the RetTy parameter to the final return type after + // promotions and casts. + static inline SMTExprRef getExpr(SMTSolverRef &Solver, ASTContext &Ctx, + SymbolRef Sym, QualType *RetTy = nullptr, + bool *hasComparison = nullptr) { + if (hasComparison) { + *hasComparison = false; + } + + return getSymExpr(Solver, Ctx, Sym, RetTy, hasComparison); + } + + // Generate an SMTExprRef that compares the expression to zero. + static inline SMTExprRef getZeroExpr(SMTSolverRef &Solver, ASTContext &Ctx, + const SMTExprRef &Exp, QualType Ty, + bool Assumption) { + + if (Ty->isRealFloatingType()) { + llvm::APFloat Zero = + llvm::APFloat::getZero(Ctx.getFloatTypeSemantics(Ty)); + return fromFloatBinOp(Solver, Exp, Assumption ? BO_EQ : BO_NE, + Solver->mkFloat(Zero)); + } + + if (Ty->isIntegralOrEnumerationType() || Ty->isAnyPointerType() || + Ty->isBlockPointerType() || Ty->isReferenceType()) { + + // Skip explicit comparison for boolean types + bool isSigned = Ty->isSignedIntegerOrEnumerationType(); + if (Ty->isBooleanType()) + return Assumption ? fromUnOp(Solver, UO_LNot, Exp) : Exp; + + return fromBinOp( + Solver, Exp, Assumption ? BO_EQ : BO_NE, + Solver->mkBitvector(llvm::APSInt("0"), Ctx.getTypeSize(Ty)), + isSigned); + } + + llvm_unreachable("Unsupported type for zero value!"); + } + + // Wrapper to generate SMTExprRef from a range. If From == To, an equality + // will be created instead. + static inline SMTExprRef getRangeExpr(SMTSolverRef &Solver, ASTContext &Ctx, + SymbolRef Sym, const llvm::APSInt &From, + const llvm::APSInt &To, bool InRange) { + // Convert lower bound + QualType FromTy; + llvm::APSInt NewFromInt; + std::tie(NewFromInt, FromTy) = fixAPSInt(Ctx, From); + SMTExprRef FromExp = + Solver->mkBitvector(NewFromInt, NewFromInt.getBitWidth()); + + // Convert symbol + QualType SymTy; + SMTExprRef Exp = getExpr(Solver, Ctx, Sym, &SymTy); + + // Construct single (in)equality + if (From == To) + return getBinExpr(Solver, Ctx, Exp, SymTy, InRange ? BO_EQ : BO_NE, + FromExp, FromTy, /*RetTy=*/nullptr); + + QualType ToTy; + llvm::APSInt NewToInt; + std::tie(NewToInt, ToTy) = fixAPSInt(Ctx, To); + SMTExprRef ToExp = Solver->mkBitvector(NewToInt, NewToInt.getBitWidth()); + assert(FromTy == ToTy && "Range values have different types!"); + + // Construct two (in)equalities, and a logical and/or + SMTExprRef LHS = + getBinExpr(Solver, Ctx, Exp, SymTy, InRange ? BO_GE : BO_LT, FromExp, + FromTy, /*RetTy=*/nullptr); + SMTExprRef RHS = getBinExpr(Solver, Ctx, Exp, SymTy, + InRange ? BO_LE : BO_GT, ToExp, ToTy, + /*RetTy=*/nullptr); + + return fromBinOp(Solver, LHS, InRange ? BO_LAnd : BO_LOr, RHS, + SymTy->isSignedIntegerOrEnumerationType()); + } + + // Recover the QualType of an APSInt. + // TODO: Refactor to put elsewhere + static inline QualType getAPSIntType(ASTContext &Ctx, + const llvm::APSInt &Int) { + return Ctx.getIntTypeForBitwidth(Int.getBitWidth(), Int.isSigned()); + } + + // Get the QualTy for the input APSInt, and fix it if it has a bitwidth of 1. + static inline std::pair<llvm::APSInt, QualType> + fixAPSInt(ASTContext &Ctx, const llvm::APSInt &Int) { + llvm::APSInt NewInt; + + // FIXME: This should be a cast from a 1-bit integer type to a boolean type, + // but the former is not available in Clang. Instead, extend the APSInt + // directly. + if (Int.getBitWidth() == 1 && getAPSIntType(Ctx, Int).isNull()) { + NewInt = Int.extend(Ctx.getTypeSize(Ctx.BoolTy)); + } else + NewInt = Int; + + return std::make_pair(NewInt, getAPSIntType(Ctx, NewInt)); + } + + // Perform implicit type conversion on binary symbolic expressions. + // May modify all input parameters. + // TODO: Refactor to use built-in conversion functions + static inline void doTypeConversion(SMTSolverRef &Solver, ASTContext &Ctx, + SMTExprRef &LHS, SMTExprRef &RHS, + QualType <y, QualType &RTy) { + assert(!LTy.isNull() && !RTy.isNull() && "Input type is null!"); + + // Perform type conversion + if ((LTy->isIntegralOrEnumerationType() && + RTy->isIntegralOrEnumerationType()) && + (LTy->isArithmeticType() && RTy->isArithmeticType())) { + SMTConv::doIntTypeConversion<SMTExprRef, &fromCast>(Solver, Ctx, LHS, LTy, + RHS, RTy); + return; + } + + if (LTy->isRealFloatingType() || RTy->isRealFloatingType()) { + SMTConv::doFloatTypeConversion<SMTExprRef, &fromCast>(Solver, Ctx, LHS, + LTy, RHS, RTy); + return; + } + + if ((LTy->isAnyPointerType() || RTy->isAnyPointerType()) || + (LTy->isBlockPointerType() || RTy->isBlockPointerType()) || + (LTy->isReferenceType() || RTy->isReferenceType())) { + // TODO: Refactor to Sema::FindCompositePointerType(), and + // Sema::CheckCompareOperands(). + + uint64_t LBitWidth = Ctx.getTypeSize(LTy); + uint64_t RBitWidth = Ctx.getTypeSize(RTy); + + // Cast the non-pointer type to the pointer type. + // TODO: Be more strict about this. + if ((LTy->isAnyPointerType() ^ RTy->isAnyPointerType()) || + (LTy->isBlockPointerType() ^ RTy->isBlockPointerType()) || + (LTy->isReferenceType() ^ RTy->isReferenceType())) { + if (LTy->isNullPtrType() || LTy->isBlockPointerType() || + LTy->isReferenceType()) { + LHS = fromCast(Solver, LHS, RTy, RBitWidth, LTy, LBitWidth); + LTy = RTy; + } else { + RHS = fromCast(Solver, RHS, LTy, LBitWidth, RTy, RBitWidth); + RTy = LTy; + } + } + + // Cast the void pointer type to the non-void pointer type. + // For void types, this assumes that the casted value is equal to the + // value of the original pointer, and does not account for alignment + // requirements. + if (LTy->isVoidPointerType() ^ RTy->isVoidPointerType()) { + assert((Ctx.getTypeSize(LTy) == Ctx.getTypeSize(RTy)) && + "Pointer types have different bitwidths!"); + if (RTy->isVoidPointerType()) + RTy = LTy; + else + LTy = RTy; + } + + if (LTy == RTy) + return; + } + + // Fallback: for the solver, assume that these types don't really matter + if ((LTy.getCanonicalType() == RTy.getCanonicalType()) || + (LTy->isObjCObjectPointerType() && RTy->isObjCObjectPointerType())) { + LTy = RTy; + return; + } + + // TODO: Refine behavior for invalid type casts + } + + // Perform implicit integer type conversion. + // May modify all input parameters. + // TODO: Refactor to use Sema::handleIntegerConversion() + template <typename T, T (*doCast)(SMTSolverRef &Solver, const T &, QualType, + uint64_t, QualType, uint64_t)> + static inline void doIntTypeConversion(SMTSolverRef &Solver, ASTContext &Ctx, + T &LHS, QualType <y, T &RHS, + QualType &RTy) { + + uint64_t LBitWidth = Ctx.getTypeSize(LTy); + uint64_t RBitWidth = Ctx.getTypeSize(RTy); + + assert(!LTy.isNull() && !RTy.isNull() && "Input type is null!"); + // Always perform integer promotion before checking type equality. + // Otherwise, e.g. (bool) a + (bool) b could trigger a backend assertion + if (LTy->isPromotableIntegerType()) { + QualType NewTy = Ctx.getPromotedIntegerType(LTy); + uint64_t NewBitWidth = Ctx.getTypeSize(NewTy); + LHS = (*doCast)(Solver, LHS, NewTy, NewBitWidth, LTy, LBitWidth); + LTy = NewTy; + LBitWidth = NewBitWidth; + } + if (RTy->isPromotableIntegerType()) { + QualType NewTy = Ctx.getPromotedIntegerType(RTy); + uint64_t NewBitWidth = Ctx.getTypeSize(NewTy); + RHS = (*doCast)(Solver, RHS, NewTy, NewBitWidth, RTy, RBitWidth); + RTy = NewTy; + RBitWidth = NewBitWidth; + } + + if (LTy == RTy) + return; + + // Perform integer type conversion + // Note: Safe to skip updating bitwidth because this must terminate + bool isLSignedTy = LTy->isSignedIntegerOrEnumerationType(); + bool isRSignedTy = RTy->isSignedIntegerOrEnumerationType(); + + int order = Ctx.getIntegerTypeOrder(LTy, RTy); + if (isLSignedTy == isRSignedTy) { + // Same signedness; use the higher-ranked type + if (order == 1) { + RHS = (*doCast)(Solver, RHS, LTy, LBitWidth, RTy, RBitWidth); + RTy = LTy; + } else { + LHS = (*doCast)(Solver, LHS, RTy, RBitWidth, LTy, LBitWidth); + LTy = RTy; + } + } else if (order != (isLSignedTy ? 1 : -1)) { + // The unsigned type has greater than or equal rank to the + // signed type, so use the unsigned type + if (isRSignedTy) { + RHS = (*doCast)(Solver, RHS, LTy, LBitWidth, RTy, RBitWidth); + RTy = LTy; + } else { + LHS = (*doCast)(Solver, LHS, RTy, RBitWidth, LTy, LBitWidth); + LTy = RTy; + } + } else if (LBitWidth != RBitWidth) { + // The two types are different widths; if we are here, that + // means the signed type is larger than the unsigned type, so + // use the signed type. + if (isLSignedTy) { + RHS = (doCast)(Solver, RHS, LTy, LBitWidth, RTy, RBitWidth); + RTy = LTy; + } else { + LHS = (*doCast)(Solver, LHS, RTy, RBitWidth, LTy, LBitWidth); + LTy = RTy; + } + } else { + // The signed type is higher-ranked than the unsigned type, + // but isn't actually any bigger (like unsigned int and long + // on most 32-bit systems). Use the unsigned type corresponding + // to the signed type. + QualType NewTy = + Ctx.getCorrespondingUnsignedType(isLSignedTy ? LTy : RTy); + RHS = (*doCast)(Solver, RHS, LTy, LBitWidth, RTy, RBitWidth); + RTy = NewTy; + LHS = (doCast)(Solver, LHS, RTy, RBitWidth, LTy, LBitWidth); + LTy = NewTy; + } + } + + // Perform implicit floating-point type conversion. + // May modify all input parameters. + // TODO: Refactor to use Sema::handleFloatConversion() + template <typename T, T (*doCast)(SMTSolverRef &Solver, const T &, QualType, + uint64_t, QualType, uint64_t)> + static inline void + doFloatTypeConversion(SMTSolverRef &Solver, ASTContext &Ctx, T &LHS, + QualType <y, T &RHS, QualType &RTy) { + + uint64_t LBitWidth = Ctx.getTypeSize(LTy); + uint64_t RBitWidth = Ctx.getTypeSize(RTy); + + // Perform float-point type promotion + if (!LTy->isRealFloatingType()) { + LHS = (*doCast)(Solver, LHS, RTy, RBitWidth, LTy, LBitWidth); + LTy = RTy; + LBitWidth = RBitWidth; + } + if (!RTy->isRealFloatingType()) { + RHS = (*doCast)(Solver, RHS, LTy, LBitWidth, RTy, RBitWidth); + RTy = LTy; + RBitWidth = LBitWidth; + } + + if (LTy == RTy) + return; + + // If we have two real floating types, convert the smaller operand to the + // bigger result + // Note: Safe to skip updating bitwidth because this must terminate + int order = Ctx.getFloatingTypeOrder(LTy, RTy); + if (order > 0) { + RHS = (*doCast)(Solver, RHS, LTy, LBitWidth, RTy, RBitWidth); + RTy = LTy; + } else if (order == 0) { + LHS = (*doCast)(Solver, LHS, RTy, RBitWidth, LTy, LBitWidth); + LTy = RTy; + } else { + llvm_unreachable("Unsupported floating-point type cast!"); + } + } +}; +} // namespace ento +} // namespace clang + +#endif
\ No newline at end of file diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SMTSolver.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SMTSolver.h index a43ca486901b..2abe5fc98744 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SMTSolver.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SMTSolver.h @@ -15,12 +15,9 @@ #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SMTSOLVER_H #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SMTSOLVER_H -#include "clang/AST/Expr.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SMTExpr.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SMTSort.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" +#include "llvm/ADT/APSInt.h" namespace clang { namespace ento { @@ -53,683 +50,6 @@ public: llvm_unreachable("Unsupported floating-point bitwidth!"); } - // Returns an appropriate sort, given a QualType and it's bit width. - SMTSortRef mkSort(const QualType &Ty, unsigned BitWidth) { - if (Ty->isBooleanType()) - return getBoolSort(); - - if (Ty->isRealFloatingType()) - return getFloatSort(BitWidth); - - return getBitvectorSort(BitWidth); - } - - /// Constructs an SMTExprRef from an unary operator. - SMTExprRef fromUnOp(const UnaryOperator::Opcode Op, const SMTExprRef &Exp) { - switch (Op) { - case UO_Minus: - return mkBVNeg(Exp); - - case UO_Not: - return mkBVNot(Exp); - - case UO_LNot: - return mkNot(Exp); - - default:; - } - llvm_unreachable("Unimplemented opcode"); - } - - /// Constructs an SMTExprRef from a floating-point unary operator. - SMTExprRef fromFloatUnOp(const UnaryOperator::Opcode Op, - const SMTExprRef &Exp) { - switch (Op) { - case UO_Minus: - return mkFPNeg(Exp); - - case UO_LNot: - return fromUnOp(Op, Exp); - - default:; - } - llvm_unreachable("Unimplemented opcode"); - } - - /// Construct an SMTExprRef from a n-ary binary operator. - SMTExprRef fromNBinOp(const BinaryOperator::Opcode Op, - const std::vector<SMTExprRef> &ASTs) { - assert(!ASTs.empty()); - - if (Op != BO_LAnd && Op != BO_LOr) - llvm_unreachable("Unimplemented opcode"); - - SMTExprRef res = ASTs.front(); - for (std::size_t i = 1; i < ASTs.size(); ++i) - res = (Op == BO_LAnd) ? mkAnd(res, ASTs[i]) : mkOr(res, ASTs[i]); - return res; - } - - /// Construct an SMTExprRef from a binary operator. - SMTExprRef fromBinOp(const SMTExprRef &LHS, const BinaryOperator::Opcode Op, - const SMTExprRef &RHS, bool isSigned) { - assert(*getSort(LHS) == *getSort(RHS) && "AST's must have the same sort!"); - - switch (Op) { - // Multiplicative operators - case BO_Mul: - return mkBVMul(LHS, RHS); - - case BO_Div: - return isSigned ? mkBVSDiv(LHS, RHS) : mkBVUDiv(LHS, RHS); - - case BO_Rem: - return isSigned ? mkBVSRem(LHS, RHS) : mkBVURem(LHS, RHS); - - // Additive operators - case BO_Add: - return mkBVAdd(LHS, RHS); - - case BO_Sub: - return mkBVSub(LHS, RHS); - - // Bitwise shift operators - case BO_Shl: - return mkBVShl(LHS, RHS); - - case BO_Shr: - return isSigned ? mkBVAshr(LHS, RHS) : mkBVLshr(LHS, RHS); - - // Relational operators - case BO_LT: - return isSigned ? mkBVSlt(LHS, RHS) : mkBVUlt(LHS, RHS); - - case BO_GT: - return isSigned ? mkBVSgt(LHS, RHS) : mkBVUgt(LHS, RHS); - - case BO_LE: - return isSigned ? mkBVSle(LHS, RHS) : mkBVUle(LHS, RHS); - - case BO_GE: - return isSigned ? mkBVSge(LHS, RHS) : mkBVUge(LHS, RHS); - - // Equality operators - case BO_EQ: - return mkEqual(LHS, RHS); - - case BO_NE: - return fromUnOp(UO_LNot, fromBinOp(LHS, BO_EQ, RHS, isSigned)); - - // Bitwise operators - case BO_And: - return mkBVAnd(LHS, RHS); - - case BO_Xor: - return mkBVXor(LHS, RHS); - - case BO_Or: - return mkBVOr(LHS, RHS); - - // Logical operators - case BO_LAnd: - return mkAnd(LHS, RHS); - - case BO_LOr: - return mkOr(LHS, RHS); - - default:; - } - llvm_unreachable("Unimplemented opcode"); - } - - /// Construct an SMTExprRef from a special floating-point binary operator. - SMTExprRef fromFloatSpecialBinOp(const SMTExprRef &LHS, - const BinaryOperator::Opcode Op, - const llvm::APFloat::fltCategory &RHS) { - switch (Op) { - // Equality operators - case BO_EQ: - switch (RHS) { - case llvm::APFloat::fcInfinity: - return mkFPIsInfinite(LHS); - - case llvm::APFloat::fcNaN: - return mkFPIsNaN(LHS); - - case llvm::APFloat::fcNormal: - return mkFPIsNormal(LHS); - - case llvm::APFloat::fcZero: - return mkFPIsZero(LHS); - } - break; - - case BO_NE: - return fromFloatUnOp(UO_LNot, fromFloatSpecialBinOp(LHS, BO_EQ, RHS)); - - default:; - } - - llvm_unreachable("Unimplemented opcode"); - } - - /// Construct an SMTExprRef from a floating-point binary operator. - SMTExprRef fromFloatBinOp(const SMTExprRef &LHS, - const BinaryOperator::Opcode Op, - const SMTExprRef &RHS) { - assert(*getSort(LHS) == *getSort(RHS) && "AST's must have the same sort!"); - - switch (Op) { - // Multiplicative operators - case BO_Mul: - return mkFPMul(LHS, RHS); - - case BO_Div: - return mkFPDiv(LHS, RHS); - - case BO_Rem: - return mkFPRem(LHS, RHS); - - // Additive operators - case BO_Add: - return mkFPAdd(LHS, RHS); - - case BO_Sub: - return mkFPSub(LHS, RHS); - - // Relational operators - case BO_LT: - return mkFPLt(LHS, RHS); - - case BO_GT: - return mkFPGt(LHS, RHS); - - case BO_LE: - return mkFPLe(LHS, RHS); - - case BO_GE: - return mkFPGe(LHS, RHS); - - // Equality operators - case BO_EQ: - return mkFPEqual(LHS, RHS); - - case BO_NE: - return fromFloatUnOp(UO_LNot, fromFloatBinOp(LHS, BO_EQ, RHS)); - - // Logical operators - case BO_LAnd: - case BO_LOr: - return fromBinOp(LHS, Op, RHS, false); - - default:; - } - - llvm_unreachable("Unimplemented opcode"); - } - - /// Construct an SMTExprRef from a QualType FromTy to a QualType ToTy, and - /// their bit widths. - SMTExprRef fromCast(const SMTExprRef &Exp, QualType ToTy, uint64_t ToBitWidth, - QualType FromTy, uint64_t FromBitWidth) { - if ((FromTy->isIntegralOrEnumerationType() && - ToTy->isIntegralOrEnumerationType()) || - (FromTy->isAnyPointerType() ^ ToTy->isAnyPointerType()) || - (FromTy->isBlockPointerType() ^ ToTy->isBlockPointerType()) || - (FromTy->isReferenceType() ^ ToTy->isReferenceType())) { - - if (FromTy->isBooleanType()) { - assert(ToBitWidth > 0 && "BitWidth must be positive!"); - return mkIte(Exp, mkBitvector(llvm::APSInt("1"), ToBitWidth), - mkBitvector(llvm::APSInt("0"), ToBitWidth)); - } - - if (ToBitWidth > FromBitWidth) - return FromTy->isSignedIntegerOrEnumerationType() - ? mkBVSignExt(ToBitWidth - FromBitWidth, Exp) - : mkBVZeroExt(ToBitWidth - FromBitWidth, Exp); - - if (ToBitWidth < FromBitWidth) - return mkBVExtract(ToBitWidth - 1, 0, Exp); - - // Both are bitvectors with the same width, ignore the type cast - return Exp; - } - - if (FromTy->isRealFloatingType() && ToTy->isRealFloatingType()) { - if (ToBitWidth != FromBitWidth) - return mkFPtoFP(Exp, getFloatSort(ToBitWidth)); - - return Exp; - } - - if (FromTy->isIntegralOrEnumerationType() && ToTy->isRealFloatingType()) { - SMTSortRef Sort = getFloatSort(ToBitWidth); - return FromTy->isSignedIntegerOrEnumerationType() ? mkFPtoSBV(Exp, Sort) - : mkFPtoUBV(Exp, Sort); - } - - if (FromTy->isRealFloatingType() && ToTy->isIntegralOrEnumerationType()) - return ToTy->isSignedIntegerOrEnumerationType() - ? mkSBVtoFP(Exp, ToBitWidth) - : mkUBVtoFP(Exp, ToBitWidth); - - llvm_unreachable("Unsupported explicit type cast!"); - } - - // Callback function for doCast parameter on APSInt type. - llvm::APSInt castAPSInt(const llvm::APSInt &V, QualType ToTy, - uint64_t ToWidth, QualType FromTy, - uint64_t FromWidth) { - APSIntType TargetType(ToWidth, !ToTy->isSignedIntegerOrEnumerationType()); - return TargetType.convert(V); - } - - // Generate an SMTExprRef that represents the given symbolic expression. - // Sets the hasComparison parameter if the expression has a comparison - // operator. - // Sets the RetTy parameter to the final return type after promotions and - // casts. - SMTExprRef getExpr(ASTContext &Ctx, SymbolRef Sym, QualType *RetTy = nullptr, - bool *hasComparison = nullptr) { - if (hasComparison) { - *hasComparison = false; - } - - return getSymExpr(Ctx, Sym, RetTy, hasComparison); - } - - // Generate an SMTExprRef that compares the expression to zero. - SMTExprRef getZeroExpr(ASTContext &Ctx, const SMTExprRef &Exp, QualType Ty, - bool Assumption) { - - if (Ty->isRealFloatingType()) { - llvm::APFloat Zero = - llvm::APFloat::getZero(Ctx.getFloatTypeSemantics(Ty)); - return fromFloatBinOp(Exp, Assumption ? BO_EQ : BO_NE, fromAPFloat(Zero)); - } - - if (Ty->isIntegralOrEnumerationType() || Ty->isAnyPointerType() || - Ty->isBlockPointerType() || Ty->isReferenceType()) { - - // Skip explicit comparison for boolean types - bool isSigned = Ty->isSignedIntegerOrEnumerationType(); - if (Ty->isBooleanType()) - return Assumption ? fromUnOp(UO_LNot, Exp) : Exp; - - return fromBinOp(Exp, Assumption ? BO_EQ : BO_NE, - fromInt("0", Ctx.getTypeSize(Ty)), isSigned); - } - - llvm_unreachable("Unsupported type for zero value!"); - } - - // Recursive implementation to unpack and generate symbolic expression. - // Sets the hasComparison and RetTy parameters. See getExpr(). - SMTExprRef getSymExpr(ASTContext &Ctx, SymbolRef Sym, QualType *RetTy, - bool *hasComparison) { - if (const SymbolData *SD = dyn_cast<SymbolData>(Sym)) { - if (RetTy) - *RetTy = Sym->getType(); - - return fromData(SD->getSymbolID(), Sym->getType(), - Ctx.getTypeSize(Sym->getType())); - } - - if (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym)) { - if (RetTy) - *RetTy = Sym->getType(); - - QualType FromTy; - SMTExprRef Exp = - getSymExpr(Ctx, SC->getOperand(), &FromTy, hasComparison); - // Casting an expression with a comparison invalidates it. Note that this - // must occur after the recursive call above. - // e.g. (signed char) (x > 0) - if (hasComparison) - *hasComparison = false; - return getCastExpr(Ctx, Exp, FromTy, Sym->getType()); - } - - if (const BinarySymExpr *BSE = dyn_cast<BinarySymExpr>(Sym)) { - SMTExprRef Exp = getSymBinExpr(Ctx, BSE, hasComparison, RetTy); - // Set the hasComparison parameter, in post-order traversal order. - if (hasComparison) - *hasComparison = BinaryOperator::isComparisonOp(BSE->getOpcode()); - return Exp; - } - - llvm_unreachable("Unsupported SymbolRef type!"); - } - - // Wrapper to generate SMTExprRef from SymbolCast data. - SMTExprRef getCastExpr(ASTContext &Ctx, const SMTExprRef &Exp, - QualType FromTy, QualType ToTy) { - return fromCast(Exp, ToTy, Ctx.getTypeSize(ToTy), FromTy, - Ctx.getTypeSize(FromTy)); - } - - // Wrapper to generate SMTExprRef from BinarySymExpr. - // Sets the hasComparison and RetTy parameters. See getSMTExprRef(). - SMTExprRef getSymBinExpr(ASTContext &Ctx, const BinarySymExpr *BSE, - bool *hasComparison, QualType *RetTy) { - QualType LTy, RTy; - BinaryOperator::Opcode Op = BSE->getOpcode(); - - if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(BSE)) { - SMTExprRef LHS = getSymExpr(Ctx, SIE->getLHS(), <y, hasComparison); - llvm::APSInt NewRInt; - std::tie(NewRInt, RTy) = fixAPSInt(Ctx, SIE->getRHS()); - SMTExprRef RHS = fromAPSInt(NewRInt); - return getBinExpr(Ctx, LHS, LTy, Op, RHS, RTy, RetTy); - } - - if (const IntSymExpr *ISE = dyn_cast<IntSymExpr>(BSE)) { - llvm::APSInt NewLInt; - std::tie(NewLInt, LTy) = fixAPSInt(Ctx, ISE->getLHS()); - SMTExprRef LHS = fromAPSInt(NewLInt); - SMTExprRef RHS = getSymExpr(Ctx, ISE->getRHS(), &RTy, hasComparison); - return getBinExpr(Ctx, LHS, LTy, Op, RHS, RTy, RetTy); - } - - if (const SymSymExpr *SSM = dyn_cast<SymSymExpr>(BSE)) { - SMTExprRef LHS = getSymExpr(Ctx, SSM->getLHS(), <y, hasComparison); - SMTExprRef RHS = getSymExpr(Ctx, SSM->getRHS(), &RTy, hasComparison); - return getBinExpr(Ctx, LHS, LTy, Op, RHS, RTy, RetTy); - } - - llvm_unreachable("Unsupported BinarySymExpr type!"); - } - - // Wrapper to generate SMTExprRef from unpacked binary symbolic expression. - // Sets the RetTy parameter. See getSMTExprRef(). - SMTExprRef getBinExpr(ASTContext &Ctx, const SMTExprRef &LHS, QualType LTy, - BinaryOperator::Opcode Op, const SMTExprRef &RHS, - QualType RTy, QualType *RetTy) { - SMTExprRef NewLHS = LHS; - SMTExprRef NewRHS = RHS; - doTypeConversion(Ctx, NewLHS, NewRHS, LTy, RTy); - - // Update the return type parameter if the output type has changed. - if (RetTy) { - // A boolean result can be represented as an integer type in C/C++, but at - // this point we only care about the SMT sorts. Set it as a boolean type - // to avoid subsequent SMT errors. - if (BinaryOperator::isComparisonOp(Op) || - BinaryOperator::isLogicalOp(Op)) { - *RetTy = Ctx.BoolTy; - } else { - *RetTy = LTy; - } - - // If the two operands are pointers and the operation is a subtraction, - // the result is of type ptrdiff_t, which is signed - if (LTy->isAnyPointerType() && RTy->isAnyPointerType() && Op == BO_Sub) { - *RetTy = Ctx.getPointerDiffType(); - } - } - - return LTy->isRealFloatingType() - ? fromFloatBinOp(NewLHS, Op, NewRHS) - : fromBinOp(NewLHS, Op, NewRHS, - LTy->isSignedIntegerOrEnumerationType()); - } - - // Wrapper to generate SMTExprRef from a range. If From == To, an equality - // will be created instead. - SMTExprRef getRangeExpr(ASTContext &Ctx, SymbolRef Sym, - const llvm::APSInt &From, const llvm::APSInt &To, - bool InRange) { - // Convert lower bound - QualType FromTy; - llvm::APSInt NewFromInt; - std::tie(NewFromInt, FromTy) = fixAPSInt(Ctx, From); - SMTExprRef FromExp = fromAPSInt(NewFromInt); - - // Convert symbol - QualType SymTy; - SMTExprRef Exp = getExpr(Ctx, Sym, &SymTy); - - // Construct single (in)equality - if (From == To) - return getBinExpr(Ctx, Exp, SymTy, InRange ? BO_EQ : BO_NE, FromExp, - FromTy, /*RetTy=*/nullptr); - - QualType ToTy; - llvm::APSInt NewToInt; - std::tie(NewToInt, ToTy) = fixAPSInt(Ctx, To); - SMTExprRef ToExp = fromAPSInt(NewToInt); - assert(FromTy == ToTy && "Range values have different types!"); - - // Construct two (in)equalities, and a logical and/or - SMTExprRef LHS = getBinExpr(Ctx, Exp, SymTy, InRange ? BO_GE : BO_LT, - FromExp, FromTy, /*RetTy=*/nullptr); - SMTExprRef RHS = - getBinExpr(Ctx, Exp, SymTy, InRange ? BO_LE : BO_GT, ToExp, ToTy, - /*RetTy=*/nullptr); - - return fromBinOp(LHS, InRange ? BO_LAnd : BO_LOr, RHS, - SymTy->isSignedIntegerOrEnumerationType()); - } - - // Recover the QualType of an APSInt. - // TODO: Refactor to put elsewhere - QualType getAPSIntType(ASTContext &Ctx, const llvm::APSInt &Int) { - return Ctx.getIntTypeForBitwidth(Int.getBitWidth(), Int.isSigned()); - } - - // Get the QualTy for the input APSInt, and fix it if it has a bitwidth of 1. - std::pair<llvm::APSInt, QualType> fixAPSInt(ASTContext &Ctx, - const llvm::APSInt &Int) { - llvm::APSInt NewInt; - - // FIXME: This should be a cast from a 1-bit integer type to a boolean type, - // but the former is not available in Clang. Instead, extend the APSInt - // directly. - if (Int.getBitWidth() == 1 && getAPSIntType(Ctx, Int).isNull()) { - NewInt = Int.extend(Ctx.getTypeSize(Ctx.BoolTy)); - } else - NewInt = Int; - - return std::make_pair(NewInt, getAPSIntType(Ctx, NewInt)); - } - - // Perform implicit type conversion on binary symbolic expressions. - // May modify all input parameters. - // TODO: Refactor to use built-in conversion functions - void doTypeConversion(ASTContext &Ctx, SMTExprRef &LHS, SMTExprRef &RHS, - QualType <y, QualType &RTy) { - assert(!LTy.isNull() && !RTy.isNull() && "Input type is null!"); - - // Perform type conversion - if ((LTy->isIntegralOrEnumerationType() && - RTy->isIntegralOrEnumerationType()) && - (LTy->isArithmeticType() && RTy->isArithmeticType())) { - doIntTypeConversion<SMTExprRef, &SMTSolver::fromCast>(Ctx, LHS, LTy, RHS, - RTy); - return; - } - - if (LTy->isRealFloatingType() || RTy->isRealFloatingType()) { - doFloatTypeConversion<SMTExprRef, &SMTSolver::fromCast>(Ctx, LHS, LTy, - RHS, RTy); - return; - } - - if ((LTy->isAnyPointerType() || RTy->isAnyPointerType()) || - (LTy->isBlockPointerType() || RTy->isBlockPointerType()) || - (LTy->isReferenceType() || RTy->isReferenceType())) { - // TODO: Refactor to Sema::FindCompositePointerType(), and - // Sema::CheckCompareOperands(). - - uint64_t LBitWidth = Ctx.getTypeSize(LTy); - uint64_t RBitWidth = Ctx.getTypeSize(RTy); - - // Cast the non-pointer type to the pointer type. - // TODO: Be more strict about this. - if ((LTy->isAnyPointerType() ^ RTy->isAnyPointerType()) || - (LTy->isBlockPointerType() ^ RTy->isBlockPointerType()) || - (LTy->isReferenceType() ^ RTy->isReferenceType())) { - if (LTy->isNullPtrType() || LTy->isBlockPointerType() || - LTy->isReferenceType()) { - LHS = fromCast(LHS, RTy, RBitWidth, LTy, LBitWidth); - LTy = RTy; - } else { - RHS = fromCast(RHS, LTy, LBitWidth, RTy, RBitWidth); - RTy = LTy; - } - } - - // Cast the void pointer type to the non-void pointer type. - // For void types, this assumes that the casted value is equal to the - // value of the original pointer, and does not account for alignment - // requirements. - if (LTy->isVoidPointerType() ^ RTy->isVoidPointerType()) { - assert((Ctx.getTypeSize(LTy) == Ctx.getTypeSize(RTy)) && - "Pointer types have different bitwidths!"); - if (RTy->isVoidPointerType()) - RTy = LTy; - else - LTy = RTy; - } - - if (LTy == RTy) - return; - } - - // Fallback: for the solver, assume that these types don't really matter - if ((LTy.getCanonicalType() == RTy.getCanonicalType()) || - (LTy->isObjCObjectPointerType() && RTy->isObjCObjectPointerType())) { - LTy = RTy; - return; - } - - // TODO: Refine behavior for invalid type casts - } - - // Perform implicit integer type conversion. - // May modify all input parameters. - // TODO: Refactor to use Sema::handleIntegerConversion() - template <typename T, T (SMTSolver::*doCast)(const T &, QualType, uint64_t, - QualType, uint64_t)> - void doIntTypeConversion(ASTContext &Ctx, T &LHS, QualType <y, T &RHS, - QualType &RTy) { - - uint64_t LBitWidth = Ctx.getTypeSize(LTy); - uint64_t RBitWidth = Ctx.getTypeSize(RTy); - - assert(!LTy.isNull() && !RTy.isNull() && "Input type is null!"); - // Always perform integer promotion before checking type equality. - // Otherwise, e.g. (bool) a + (bool) b could trigger a backend assertion - if (LTy->isPromotableIntegerType()) { - QualType NewTy = Ctx.getPromotedIntegerType(LTy); - uint64_t NewBitWidth = Ctx.getTypeSize(NewTy); - LHS = (this->*doCast)(LHS, NewTy, NewBitWidth, LTy, LBitWidth); - LTy = NewTy; - LBitWidth = NewBitWidth; - } - if (RTy->isPromotableIntegerType()) { - QualType NewTy = Ctx.getPromotedIntegerType(RTy); - uint64_t NewBitWidth = Ctx.getTypeSize(NewTy); - RHS = (this->*doCast)(RHS, NewTy, NewBitWidth, RTy, RBitWidth); - RTy = NewTy; - RBitWidth = NewBitWidth; - } - - if (LTy == RTy) - return; - - // Perform integer type conversion - // Note: Safe to skip updating bitwidth because this must terminate - bool isLSignedTy = LTy->isSignedIntegerOrEnumerationType(); - bool isRSignedTy = RTy->isSignedIntegerOrEnumerationType(); - - int order = Ctx.getIntegerTypeOrder(LTy, RTy); - if (isLSignedTy == isRSignedTy) { - // Same signedness; use the higher-ranked type - if (order == 1) { - RHS = (this->*doCast)(RHS, LTy, LBitWidth, RTy, RBitWidth); - RTy = LTy; - } else { - LHS = (this->*doCast)(LHS, RTy, RBitWidth, LTy, LBitWidth); - LTy = RTy; - } - } else if (order != (isLSignedTy ? 1 : -1)) { - // The unsigned type has greater than or equal rank to the - // signed type, so use the unsigned type - if (isRSignedTy) { - RHS = (this->*doCast)(RHS, LTy, LBitWidth, RTy, RBitWidth); - RTy = LTy; - } else { - LHS = (this->*doCast)(LHS, RTy, RBitWidth, LTy, LBitWidth); - LTy = RTy; - } - } else if (LBitWidth != RBitWidth) { - // The two types are different widths; if we are here, that - // means the signed type is larger than the unsigned type, so - // use the signed type. - if (isLSignedTy) { - RHS = (this->*doCast)(RHS, LTy, LBitWidth, RTy, RBitWidth); - RTy = LTy; - } else { - LHS = (this->*doCast)(LHS, RTy, RBitWidth, LTy, LBitWidth); - LTy = RTy; - } - } else { - // The signed type is higher-ranked than the unsigned type, - // but isn't actually any bigger (like unsigned int and long - // on most 32-bit systems). Use the unsigned type corresponding - // to the signed type. - QualType NewTy = - Ctx.getCorrespondingUnsignedType(isLSignedTy ? LTy : RTy); - RHS = (this->*doCast)(RHS, LTy, LBitWidth, RTy, RBitWidth); - RTy = NewTy; - LHS = (this->*doCast)(LHS, RTy, RBitWidth, LTy, LBitWidth); - LTy = NewTy; - } - } - - // Perform implicit floating-point type conversion. - // May modify all input parameters. - // TODO: Refactor to use Sema::handleFloatConversion() - template <typename T, T (SMTSolver::*doCast)(const T &, QualType, uint64_t, - QualType, uint64_t)> - void doFloatTypeConversion(ASTContext &Ctx, T &LHS, QualType <y, T &RHS, - QualType &RTy) { - - uint64_t LBitWidth = Ctx.getTypeSize(LTy); - uint64_t RBitWidth = Ctx.getTypeSize(RTy); - - // Perform float-point type promotion - if (!LTy->isRealFloatingType()) { - LHS = (this->*doCast)(LHS, RTy, RBitWidth, LTy, LBitWidth); - LTy = RTy; - LBitWidth = RBitWidth; - } - if (!RTy->isRealFloatingType()) { - RHS = (this->*doCast)(RHS, LTy, LBitWidth, RTy, RBitWidth); - RTy = LTy; - RBitWidth = LBitWidth; - } - - if (LTy == RTy) - return; - - // If we have two real floating types, convert the smaller operand to the - // bigger result - // Note: Safe to skip updating bitwidth because this must terminate - int order = Ctx.getFloatingTypeOrder(LTy, RTy); - if (order > 0) { - RHS = (this->*doCast)(RHS, LTy, LBitWidth, RTy, RBitWidth); - RTy = LTy; - } else if (order == 0) { - LHS = (this->*doCast)(LHS, RTy, RBitWidth, LTy, LBitWidth); - LTy = RTy; - } else { - llvm_unreachable("Unsupported floating-point type cast!"); - } - } - // Returns a boolean sort. virtual SMTSortRef getBoolSort() = 0; @@ -906,23 +226,23 @@ public: /// operation virtual SMTExprRef mkFPtoFP(const SMTExprRef &From, const SMTSortRef &To) = 0; - /// Creates a floating-point conversion from floatint-point to signed - /// bitvector operation - virtual SMTExprRef mkFPtoSBV(const SMTExprRef &From, - const SMTSortRef &To) = 0; - - /// Creates a floating-point conversion from floatint-point to unsigned - /// bitvector operation - virtual SMTExprRef mkFPtoUBV(const SMTExprRef &From, - const SMTSortRef &To) = 0; - /// Creates a floating-point conversion from signed bitvector to /// floatint-point operation - virtual SMTExprRef mkSBVtoFP(const SMTExprRef &From, unsigned ToWidth) = 0; + virtual SMTExprRef mkSBVtoFP(const SMTExprRef &From, + const SMTSortRef &To) = 0; /// Creates a floating-point conversion from unsigned bitvector to /// floatint-point operation - virtual SMTExprRef mkUBVtoFP(const SMTExprRef &From, unsigned ToWidth) = 0; + virtual SMTExprRef mkUBVtoFP(const SMTExprRef &From, + const SMTSortRef &To) = 0; + + /// Creates a floating-point conversion from floatint-point to signed + /// bitvector operation + virtual SMTExprRef mkFPtoSBV(const SMTExprRef &From, unsigned ToWidth) = 0; + + /// Creates a floating-point conversion from floatint-point to unsigned + /// bitvector operation + virtual SMTExprRef mkFPtoUBV(const SMTExprRef &From, unsigned ToWidth) = 0; /// Creates a new symbol, given a name and a sort virtual SMTExprRef mkSymbol(const char *Name, SMTSortRef Sort) = 0; @@ -953,24 +273,8 @@ public: virtual bool getInterpretation(const SMTExprRef &Exp, llvm::APFloat &Float) = 0; - /// Construct an SMTExprRef value from a boolean. - virtual SMTExprRef fromBoolean(const bool Bool) = 0; - - /// Construct an SMTExprRef value from a finite APFloat. - virtual SMTExprRef fromAPFloat(const llvm::APFloat &Float) = 0; - - /// Construct an SMTExprRef value from an APSInt. - virtual SMTExprRef fromAPSInt(const llvm::APSInt &Int) = 0; - - /// Construct an SMTExprRef value from an integer. - virtual SMTExprRef fromInt(const char *Int, uint64_t BitWidth) = 0; - - /// Construct an SMTExprRef from a SymbolData. - virtual SMTExprRef fromData(const SymbolID ID, const QualType &Ty, - uint64_t BitWidth) = 0; - /// Check if the constraints are satisfiable - virtual ConditionTruthVal check() const = 0; + virtual Optional<bool> check() const = 0; /// Push the current solver state virtual void push() = 0; @@ -979,7 +283,10 @@ public: virtual void pop(unsigned NumStates = 1) = 0; /// Reset the solver and remove all constraints. - virtual void reset() const = 0; + virtual void reset() = 0; + + /// Checks if the solver supports floating-points. + virtual bool isFPSupported() = 0; virtual void print(raw_ostream &OS) const = 0; }; @@ -988,7 +295,7 @@ public: using SMTSolverRef = std::shared_ptr<SMTSolver>; /// Convenience method to create and Z3Solver object -std::unique_ptr<SMTSolver> CreateZ3Solver(); +SMTSolverRef CreateZ3Solver(); } // namespace ento } // namespace clang diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h index 865014b22830..c9e284a1a3e8 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h @@ -139,8 +139,8 @@ public: virtual SVal simplifySVal(ProgramStateRef State, SVal Val) = 0; /// Constructs a symbolic expression for two non-location values. - SVal makeSymExprValNN(ProgramStateRef state, BinaryOperator::Opcode op, - NonLoc lhs, NonLoc rhs, QualType resultTy); + SVal makeSymExprValNN(BinaryOperator::Opcode op, + NonLoc lhs, NonLoc rhs, QualType resultTy); SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, SVal lhs, SVal rhs, QualType type); diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h index 1b79bfc3f8cf..0efe96f67f8e 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h @@ -530,9 +530,7 @@ public: return PTMDataType::getFromOpaqueValue(const_cast<void *>(Data)); } - bool isNullMemberPointer() const { - return getPTMData().isNull(); - } + bool isNullMemberPointer() const; const DeclaratorDecl *getDecl() const; diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h index fc072a380074..f49f761c77eb 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h @@ -130,6 +130,8 @@ public: /// used to query and manipulate MemRegion objects. MemRegionManager& getRegionManager() { return MRMgr; } + SValBuilder& getSValBuilder() { return svalBuilder; } + virtual Loc getLValueVar(const VarDecl *VD, const LocationContext *LC) { return svalBuilder.makeLoc(MRMgr.getVarRegion(VD, LC)); } @@ -252,19 +254,18 @@ public: virtual bool scanReachableSymbols(Store S, const MemRegion *R, ScanReachableSymbols &Visitor) = 0; - virtual void print(Store store, raw_ostream &Out, - const char* nl, const char *sep) = 0; + virtual void print(Store store, raw_ostream &Out, const char* nl) = 0; class BindingsHandler { public: virtual ~BindingsHandler(); + /// \return whether the iteration should continue. virtual bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion *region, SVal val) = 0; }; - class FindUniqueBinding : - public BindingsHandler { + class FindUniqueBinding : public BindingsHandler { SymbolRef Sym; const MemRegion* Binding = nullptr; bool First = true; diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h index d6aa4feddff2..d745b0f51ab0 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h @@ -72,7 +72,7 @@ public: /// Called by CoreEngine. Used to generate successor /// nodes by processing the 'effects' of a branch condition. - virtual void processBranch(const Stmt *Condition, const Stmt *Term, + virtual void processBranch(const Stmt *Condition, NodeBuilderContext& BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, @@ -156,7 +156,6 @@ public: notifyCheckersOfPointerEscape(ProgramStateRef State, const InvalidatedSymbols *Invalidated, ArrayRef<const MemRegion *> ExplicitRegions, - ArrayRef<const MemRegion *> Regions, const CallEvent *Call, RegionAndSymbolInvalidationTraits &HTraits) = 0; @@ -167,7 +166,7 @@ public: /// Called by CoreEngine when the analysis worklist is either empty or the // maximum number of analysis steps have been reached. - virtual void processEndWorklist(bool hasWorkRemaining) = 0; + virtual void processEndWorklist() = 0; }; } // end GR namespace diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h index 074551962607..d02a8abd1148 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h @@ -309,7 +309,10 @@ protected: BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t) : SymExpr(k), Op(op), T(t) { assert(classof(this)); - assert(isValidTypeForSymbol(t)); + // Binary expressions are results of arithmetic. Pointer arithmetic is not + // handled by binary expressions, but it is instead handled by applying + // sub-regions to regions. + assert(isValidTypeForSymbol(t) && !Loc::isLocType(t)); } public: @@ -555,7 +558,6 @@ class SymbolReaper { SymbolMapTy TheLiving; SymbolSetTy MetadataInUse; - SymbolSetTy TheDead; RegionSetTy RegionRoots; @@ -600,21 +602,6 @@ public: /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback. void markInUse(SymbolRef sym); - /// If a symbol is known to be live, marks the symbol as live. - /// - /// Otherwise, if the symbol cannot be proven live, it is marked as dead. - /// Returns true if the symbol is dead, false if live. - bool maybeDead(SymbolRef sym); - - using dead_iterator = SymbolSetTy::const_iterator; - - dead_iterator dead_begin() const { return TheDead.begin(); } - dead_iterator dead_end() const { return TheDead.end(); } - - bool hasDeadSymbols() const { - return !TheDead.empty(); - } - using region_iterator = RegionSetTy::const_iterator; region_iterator region_begin() const { return RegionRoots.begin(); } @@ -623,9 +610,9 @@ public: /// Returns whether or not a symbol has been confirmed dead. /// /// This should only be called once all marking of dead symbols has completed. - /// (For checkers, this means only in the evalDeadSymbols callback.) - bool isDead(SymbolRef sym) const { - return TheDead.count(sym); + /// (For checkers, this means only in the checkDeadSymbols callback.) + bool isDead(SymbolRef sym) { + return !isLive(sym); } void markLive(const MemRegion *region); @@ -654,7 +641,7 @@ public: /// The method returns \c true if symbols should continue be scanned and \c /// false otherwise. virtual bool VisitSymbol(SymbolRef sym) = 0; - virtual bool VisitMemRegion(const MemRegion *region) { return true; } + virtual bool VisitMemRegion(const MemRegion *) { return true; } }; } // namespace ento diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h index ce19b7131d42..8218fb1eeafe 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h @@ -34,10 +34,7 @@ using TaintMapImpl = llvm::ImmutableMap<SymbolRef, TaintTagType>; template<> struct ProgramStateTrait<TaintMap> : public ProgramStatePartialTrait<TaintMapImpl> { - static void *GDMIndex() { - static int index = 0; - return &index; - } + static void *GDMIndex(); }; /// The GDM component mapping derived symbols' parent symbols to their @@ -49,10 +46,7 @@ using DerivedSymTaintImpl = llvm::ImmutableMap<SymbolRef, TaintedSubRegions>; template<> struct ProgramStateTrait<DerivedSymTaint> : public ProgramStatePartialTrait<DerivedSymTaintImpl> { - static void *GDMIndex() { - static int index; - return &index; - } + static void *GDMIndex(); }; class TaintManager { diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h b/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h index 07edd35ff944..ef3c2694b283 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h @@ -85,6 +85,7 @@ public: static std::unique_ptr<WorkList> makeBFSBlockDFSContents(); static std::unique_ptr<WorkList> makeUnexploredFirst(); static std::unique_ptr<WorkList> makeUnexploredFirstPriorityQueue(); + static std::unique_ptr<WorkList> makeUnexploredFirstPriorityLocationQueue(); }; } // end ento namespace diff --git a/include/clang/StaticAnalyzer/Core/RetainSummaryManager.h b/include/clang/StaticAnalyzer/Core/RetainSummaryManager.h new file mode 100644 index 000000000000..4fcaa794c17b --- /dev/null +++ b/include/clang/StaticAnalyzer/Core/RetainSummaryManager.h @@ -0,0 +1,798 @@ +//=== RetainSummaryManager.h - Summaries for reference counting ---*- C++ -*--// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines summaries implementation for retain counting, which +// implements a reference count checker for Core Foundation and Cocoa +// on (Mac OS X). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYZER_CORE_RETAINSUMMARYMANAGER +#define LLVM_CLANG_ANALYZER_CORE_RETAINSUMMARYMANAGER + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/FoldingSet.h" +#include "clang/AST/Attr.h" +#include "clang/AST/DeclCXX.h" +#include "clang/AST/DeclObjC.h" +#include "clang/AST/ParentMap.h" +#include "clang/Analysis/SelectorExtras.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "llvm/ADT/STLExtras.h" + +//===----------------------------------------------------------------------===// +// Adapters for FoldingSet. +//===----------------------------------------------------------------------===// + +using namespace clang; +using namespace ento; + +namespace clang { +namespace ento { + +/// Determines the object kind of a tracked object. +enum class ObjKind { + /// Indicates that the tracked object is a CF object. + CF, + + /// Indicates that the tracked object is an Objective-C object. + ObjC, + + /// Indicates that the tracked object could be a CF or Objective-C object. + AnyObj, + + /// Indicates that the tracked object is a generalized object. + Generalized, + + /// Indicates that the tracking object is a descendant of a + /// referenced-counted OSObject, used in the Darwin kernel. + OS +}; + +enum ArgEffectKind { + /// There is no effect. + DoNothing, + + /// The argument is treated as if an -autorelease message had been sent to + /// the referenced object. + Autorelease, + + /// The argument is treated as if the referenced object was deallocated. + Dealloc, + + /// The argument has its reference count decreased by 1. + DecRef, + + /// The argument has its reference count decreased by 1 to model + /// a transferred bridge cast under ARC. + DecRefBridgedTransferred, + + /// The argument has its reference count increased by 1. + IncRef, + + /// The argument is a pointer to a retain-counted object; on exit, the new + /// value of the pointer is a +0 value. + UnretainedOutParameter, + + /// The argument is a pointer to a retain-counted object; on exit, the new + /// value of the pointer is a +1 value. + RetainedOutParameter, + + /// The argument is a pointer to a retain-counted object; on exit, the new + /// value of the pointer is a +1 value iff the return code is zero. + RetainedOutParameterOnZero, + + /// The argument is a pointer to a retain-counted object; on exit, the new + /// value of the pointer is a +1 value iff the return code is non-zero. + RetainedOutParameterOnNonZero, + + /// The argument is treated as potentially escaping, meaning that + /// even when its reference count hits 0 it should be treated as still + /// possibly being alive as someone else *may* be holding onto the object. + MayEscape, + + /// All typestate tracking of the object ceases. This is usually employed + /// when the effect of the call is completely unknown. + StopTracking, + + /// All typestate tracking of the object ceases. Unlike StopTracking, + /// this is also enforced when the method body is inlined. + /// + /// In some cases, we obtain a better summary for this checker + /// by looking at the call site than by inlining the function. + /// Signifies that we should stop tracking the symbol even if + /// the function is inlined. + StopTrackingHard, + + /// Performs the combined functionality of DecRef and StopTrackingHard. + /// + /// The models the effect that the called function decrements the reference + /// count of the argument and all typestate tracking on that argument + /// should cease. + DecRefAndStopTrackingHard, +}; + +/// An ArgEffect summarizes the retain count behavior on an argument or receiver +/// to a function or method. +class ArgEffect { + ArgEffectKind K; + ObjKind O; +public: + explicit ArgEffect(ArgEffectKind K = DoNothing, ObjKind O = ObjKind::AnyObj) + : K(K), O(O) {} + + ArgEffectKind getKind() const { return K; } + ObjKind getObjKind() const { return O; } + + ArgEffect withKind(ArgEffectKind NewK) { + return ArgEffect(NewK, O); + } + + bool operator==(const ArgEffect &Other) const { + return K == Other.K && O == Other.O; + } +}; + +/// RetEffect summarizes a call's retain/release behavior with respect +/// to its return value. +class RetEffect { +public: + enum Kind { + /// Indicates that no retain count information is tracked for + /// the return value. + NoRet, + + /// Indicates that the returned value is an owned (+1) symbol. + OwnedSymbol, + + /// Indicates that the returned value is an object with retain count + /// semantics but that it is not owned (+0). This is the default + /// for getters, etc. + NotOwnedSymbol, + + /// Indicates that the return value is an owned object when the + /// receiver is also a tracked object. + OwnedWhenTrackedReceiver, + + // Treat this function as returning a non-tracked symbol even if + // the function has been inlined. This is used where the call + // site summary is more precise than the summary indirectly produced + // by inlining the function + NoRetHard + }; + +private: + Kind K; + ObjKind O; + + RetEffect(Kind k, ObjKind o = ObjKind::AnyObj) : K(k), O(o) {} + +public: + Kind getKind() const { return K; } + + ObjKind getObjKind() const { return O; } + + bool isOwned() const { + return K == OwnedSymbol || K == OwnedWhenTrackedReceiver; + } + + bool notOwned() const { + return K == NotOwnedSymbol; + } + + bool operator==(const RetEffect &Other) const { + return K == Other.K && O == Other.O; + } + + static RetEffect MakeOwnedWhenTrackedReceiver() { + return RetEffect(OwnedWhenTrackedReceiver, ObjKind::ObjC); + } + + static RetEffect MakeOwned(ObjKind o) { + return RetEffect(OwnedSymbol, o); + } + static RetEffect MakeNotOwned(ObjKind o) { + return RetEffect(NotOwnedSymbol, o); + } + static RetEffect MakeNoRet() { + return RetEffect(NoRet); + } + static RetEffect MakeNoRetHard() { + return RetEffect(NoRetHard); + } +}; + +/// Encapsulates the retain count semantics on the arguments, return value, +/// and receiver (if any) of a function/method call. +/// +/// Note that construction of these objects is not highly efficient. That +/// is okay for clients where creating these objects isn't really a bottleneck. +/// The purpose of the API is to provide something simple. The actual +/// static analyzer checker that implements retain/release typestate +/// tracking uses something more efficient. +class CallEffects { + llvm::SmallVector<ArgEffect, 10> Args; + RetEffect Ret; + ArgEffect Receiver; + + CallEffects(const RetEffect &R, + ArgEffect Receiver = ArgEffect(DoNothing, ObjKind::AnyObj)) + : Ret(R), Receiver(Receiver) {} + +public: + /// Returns the argument effects for a call. + ArrayRef<ArgEffect> getArgs() const { return Args; } + + /// Returns the effects on the receiver. + ArgEffect getReceiver() const { return Receiver; } + + /// Returns the effect on the return value. + RetEffect getReturnValue() const { return Ret; } + + /// Return the CallEfect for a given Objective-C method. + static CallEffects getEffect(const ObjCMethodDecl *MD); + + /// Return the CallEfect for a given C/C++ function. + static CallEffects getEffect(const FunctionDecl *FD); +}; + +/// A key identifying a summary. +class ObjCSummaryKey { + IdentifierInfo* II; + Selector S; +public: + ObjCSummaryKey(IdentifierInfo* ii, Selector s) + : II(ii), S(s) {} + + ObjCSummaryKey(const ObjCInterfaceDecl *d, Selector s) + : II(d ? d->getIdentifier() : nullptr), S(s) {} + + ObjCSummaryKey(Selector s) + : II(nullptr), S(s) {} + + IdentifierInfo *getIdentifier() const { return II; } + Selector getSelector() const { return S; } +}; + +} // end namespace ento +} // end namespace clang + + +namespace llvm { + +template <> struct FoldingSetTrait<ArgEffect> { +static inline void Profile(const ArgEffect X, FoldingSetNodeID &ID) { + ID.AddInteger((unsigned) X.getKind()); + ID.AddInteger((unsigned) X.getObjKind()); +} +}; +template <> struct FoldingSetTrait<RetEffect> { + static inline void Profile(const RetEffect &X, FoldingSetNodeID &ID) { + ID.AddInteger((unsigned) X.getKind()); + ID.AddInteger((unsigned) X.getObjKind()); +} +}; + +template <> struct DenseMapInfo<ObjCSummaryKey> { + static inline ObjCSummaryKey getEmptyKey() { + return ObjCSummaryKey(DenseMapInfo<IdentifierInfo*>::getEmptyKey(), + DenseMapInfo<Selector>::getEmptyKey()); + } + + static inline ObjCSummaryKey getTombstoneKey() { + return ObjCSummaryKey(DenseMapInfo<IdentifierInfo*>::getTombstoneKey(), + DenseMapInfo<Selector>::getTombstoneKey()); + } + + static unsigned getHashValue(const ObjCSummaryKey &V) { + typedef std::pair<IdentifierInfo*, Selector> PairTy; + return DenseMapInfo<PairTy>::getHashValue(PairTy(V.getIdentifier(), + V.getSelector())); + } + + static bool isEqual(const ObjCSummaryKey& LHS, const ObjCSummaryKey& RHS) { + return LHS.getIdentifier() == RHS.getIdentifier() && + LHS.getSelector() == RHS.getSelector(); + } + +}; + +} // end llvm namespace + + +namespace clang { +namespace ento { + +/// ArgEffects summarizes the effects of a function/method call on all of +/// its arguments. +typedef llvm::ImmutableMap<unsigned, ArgEffect> ArgEffects; + +/// Summary for a function with respect to ownership changes. +class RetainSummary { + /// Args - a map of (index, ArgEffect) pairs, where index + /// specifies the argument (starting from 0). This can be sparsely + /// populated; arguments with no entry in Args use 'DefaultArgEffect'. + ArgEffects Args; + + /// DefaultArgEffect - The default ArgEffect to apply to arguments that + /// do not have an entry in Args. + ArgEffect DefaultArgEffect; + + /// Receiver - If this summary applies to an Objective-C message expression, + /// this is the effect applied to the state of the receiver. + ArgEffect Receiver; + + /// Effect on "this" pointer - applicable only to C++ method calls. + ArgEffect This; + + /// Ret - The effect on the return value. Used to indicate if the + /// function/method call returns a new tracked symbol. + RetEffect Ret; + +public: + RetainSummary(ArgEffects A, + RetEffect R, + ArgEffect defaultEff, + ArgEffect ReceiverEff, + ArgEffect ThisEff) + : Args(A), DefaultArgEffect(defaultEff), Receiver(ReceiverEff), + This(ThisEff), Ret(R) {} + + /// getArg - Return the argument effect on the argument specified by + /// idx (starting from 0). + ArgEffect getArg(unsigned idx) const { + if (const ArgEffect *AE = Args.lookup(idx)) + return *AE; + + return DefaultArgEffect; + } + + void addArg(ArgEffects::Factory &af, unsigned idx, ArgEffect e) { + Args = af.add(Args, idx, e); + } + + /// setDefaultArgEffect - Set the default argument effect. + void setDefaultArgEffect(ArgEffect E) { + DefaultArgEffect = E; + } + + /// getRetEffect - Returns the effect on the return value of the call. + RetEffect getRetEffect() const { return Ret; } + + /// setRetEffect - Set the effect of the return value of the call. + void setRetEffect(RetEffect E) { Ret = E; } + + + /// Sets the effect on the receiver of the message. + void setReceiverEffect(ArgEffect e) { Receiver = e; } + + /// getReceiverEffect - Returns the effect on the receiver of the call. + /// This is only meaningful if the summary applies to an ObjCMessageExpr*. + ArgEffect getReceiverEffect() const { return Receiver; } + + /// \return the effect on the "this" receiver of the method call. + /// This is only meaningful if the summary applies to CXXMethodDecl*. + ArgEffect getThisEffect() const { return This; } + + /// Set the effect of the method on "this". + void setThisEffect(ArgEffect e) { This = e; } + + bool isNoop() const { + return Ret == RetEffect::MakeNoRet() && Receiver.getKind() == DoNothing + && DefaultArgEffect.getKind() == MayEscape && This.getKind() == DoNothing + && Args.isEmpty(); + } + + /// Test if two retain summaries are identical. Note that merely equivalent + /// summaries are not necessarily identical (for example, if an explicit + /// argument effect matches the default effect). + bool operator==(const RetainSummary &Other) const { + return Args == Other.Args && DefaultArgEffect == Other.DefaultArgEffect && + Receiver == Other.Receiver && This == Other.This && Ret == Other.Ret; + } + + /// Profile this summary for inclusion in a FoldingSet. + void Profile(llvm::FoldingSetNodeID& ID) const { + ID.Add(Args); + ID.Add(DefaultArgEffect); + ID.Add(Receiver); + ID.Add(This); + ID.Add(Ret); + } + + /// A retain summary is simple if it has no ArgEffects other than the default. + bool isSimple() const { + return Args.isEmpty(); + } + + ArgEffects getArgEffects() const { return Args; } + +private: + ArgEffect getDefaultArgEffect() const { return DefaultArgEffect; } + + friend class RetainSummaryManager; +}; + +class ObjCSummaryCache { + typedef llvm::DenseMap<ObjCSummaryKey, const RetainSummary *> MapTy; + MapTy M; +public: + ObjCSummaryCache() {} + + const RetainSummary * find(const ObjCInterfaceDecl *D, Selector S) { + // Do a lookup with the (D,S) pair. If we find a match return + // the iterator. + ObjCSummaryKey K(D, S); + MapTy::iterator I = M.find(K); + + if (I != M.end()) + return I->second; + if (!D) + return nullptr; + + // Walk the super chain. If we find a hit with a parent, we'll end + // up returning that summary. We actually allow that key (null,S), as + // we cache summaries for the null ObjCInterfaceDecl* to allow us to + // generate initial summaries without having to worry about NSObject + // being declared. + // FIXME: We may change this at some point. + for (ObjCInterfaceDecl *C=D->getSuperClass() ;; C=C->getSuperClass()) { + if ((I = M.find(ObjCSummaryKey(C, S))) != M.end()) + break; + + if (!C) + return nullptr; + } + + // Cache the summary with original key to make the next lookup faster + // and return the iterator. + const RetainSummary *Summ = I->second; + M[K] = Summ; + return Summ; + } + + const RetainSummary *find(IdentifierInfo* II, Selector S) { + // FIXME: Class method lookup. Right now we don't have a good way + // of going between IdentifierInfo* and the class hierarchy. + MapTy::iterator I = M.find(ObjCSummaryKey(II, S)); + + if (I == M.end()) + I = M.find(ObjCSummaryKey(S)); + + return I == M.end() ? nullptr : I->second; + } + + const RetainSummary *& operator[](ObjCSummaryKey K) { + return M[K]; + } + + const RetainSummary *& operator[](Selector S) { + return M[ ObjCSummaryKey(S) ]; + } +}; + +class RetainSummaryTemplate; + +class RetainSummaryManager { + typedef llvm::DenseMap<const FunctionDecl*, const RetainSummary *> + FuncSummariesTy; + + typedef ObjCSummaryCache ObjCMethodSummariesTy; + + typedef llvm::FoldingSetNodeWrapper<RetainSummary> CachedSummaryNode; + + /// Ctx - The ASTContext object for the analyzed ASTs. + ASTContext &Ctx; + + /// Records whether or not the analyzed code runs in ARC mode. + const bool ARCEnabled; + + /// Track Objective-C and CoreFoundation objects. + const bool TrackObjCAndCFObjects; + + /// Track sublcasses of OSObject. + const bool TrackOSObjects; + + /// FuncSummaries - A map from FunctionDecls to summaries. + FuncSummariesTy FuncSummaries; + + /// ObjCClassMethodSummaries - A map from selectors (for instance methods) + /// to summaries. + ObjCMethodSummariesTy ObjCClassMethodSummaries; + + /// ObjCMethodSummaries - A map from selectors to summaries. + ObjCMethodSummariesTy ObjCMethodSummaries; + + /// BPAlloc - A BumpPtrAllocator used for allocating summaries, ArgEffects, + /// and all other data used by the checker. + llvm::BumpPtrAllocator BPAlloc; + + /// AF - A factory for ArgEffects objects. + ArgEffects::Factory AF; + + /// ObjCAllocRetE - Default return effect for methods returning Objective-C + /// objects. + RetEffect ObjCAllocRetE; + + /// ObjCInitRetE - Default return effect for init methods returning + /// Objective-C objects. + RetEffect ObjCInitRetE; + + /// SimpleSummaries - Used for uniquing summaries that don't have special + /// effects. + llvm::FoldingSet<CachedSummaryNode> SimpleSummaries; + + /// Create an OS object at +1. + const RetainSummary *getOSSummaryCreateRule(const FunctionDecl *FD); + + /// Get an OS object at +0. + const RetainSummary *getOSSummaryGetRule(const FunctionDecl *FD); + + /// Increment the reference count on OS object. + const RetainSummary *getOSSummaryRetainRule(const FunctionDecl *FD); + + /// Decrement the reference count on OS object. + const RetainSummary *getOSSummaryReleaseRule(const FunctionDecl *FD); + + /// Free the OS object. + const RetainSummary *getOSSummaryFreeRule(const FunctionDecl *FD); + + const RetainSummary *getUnarySummary(const FunctionType* FT, + ArgEffectKind AE); + + const RetainSummary *getCFSummaryCreateRule(const FunctionDecl *FD); + const RetainSummary *getCFSummaryGetRule(const FunctionDecl *FD); + const RetainSummary *getCFCreateGetRuleSummary(const FunctionDecl *FD); + + const RetainSummary *getPersistentSummary(const RetainSummary &OldSumm); + + const RetainSummary * + getPersistentSummary(RetEffect RetEff, ArgEffects ScratchArgs, + ArgEffect ReceiverEff = ArgEffect(DoNothing), + ArgEffect DefaultEff = ArgEffect(MayEscape), + ArgEffect ThisEff = ArgEffect(DoNothing)) { + RetainSummary Summ(ScratchArgs, RetEff, DefaultEff, ReceiverEff, ThisEff); + return getPersistentSummary(Summ); + } + + const RetainSummary *getDoNothingSummary() { + return getPersistentSummary(RetEffect::MakeNoRet(), + ArgEffects(AF.getEmptyMap()), + ArgEffect(DoNothing), ArgEffect(DoNothing)); + } + + const RetainSummary *getDefaultSummary() { + return getPersistentSummary(RetEffect::MakeNoRet(), + ArgEffects(AF.getEmptyMap()), + ArgEffect(DoNothing), ArgEffect(MayEscape)); + } + + const RetainSummary *getPersistentStopSummary() { + return getPersistentSummary( + RetEffect::MakeNoRet(), ArgEffects(AF.getEmptyMap()), + ArgEffect(StopTracking), ArgEffect(StopTracking)); + } + + void InitializeClassMethodSummaries(); + void InitializeMethodSummaries(); + + void addNSObjectClsMethSummary(Selector S, const RetainSummary *Summ) { + ObjCClassMethodSummaries[S] = Summ; + } + + void addNSObjectMethSummary(Selector S, const RetainSummary *Summ) { + ObjCMethodSummaries[S] = Summ; + } + + void addClassMethSummary(const char* Cls, const char* name, + const RetainSummary *Summ, bool isNullary = true) { + IdentifierInfo* ClsII = &Ctx.Idents.get(Cls); + Selector S = isNullary ? GetNullarySelector(name, Ctx) + : GetUnarySelector(name, Ctx); + ObjCClassMethodSummaries[ObjCSummaryKey(ClsII, S)] = Summ; + } + + void addInstMethSummary(const char* Cls, const char* nullaryName, + const RetainSummary *Summ) { + IdentifierInfo* ClsII = &Ctx.Idents.get(Cls); + Selector S = GetNullarySelector(nullaryName, Ctx); + ObjCMethodSummaries[ObjCSummaryKey(ClsII, S)] = Summ; + } + + template <typename... Keywords> + void addMethodSummary(IdentifierInfo *ClsII, ObjCMethodSummariesTy &Summaries, + const RetainSummary *Summ, Keywords *... Kws) { + Selector S = getKeywordSelector(Ctx, Kws...); + Summaries[ObjCSummaryKey(ClsII, S)] = Summ; + } + + template <typename... Keywords> + void addInstMethSummary(const char *Cls, const RetainSummary *Summ, + Keywords *... Kws) { + addMethodSummary(&Ctx.Idents.get(Cls), ObjCMethodSummaries, Summ, Kws...); + } + + template <typename... Keywords> + void addClsMethSummary(const char *Cls, const RetainSummary *Summ, + Keywords *... Kws) { + addMethodSummary(&Ctx.Idents.get(Cls), ObjCClassMethodSummaries, Summ, + Kws...); + } + + template <typename... Keywords> + void addClsMethSummary(IdentifierInfo *II, const RetainSummary *Summ, + Keywords *... Kws) { + addMethodSummary(II, ObjCClassMethodSummaries, Summ, Kws...); + } + + const RetainSummary * generateSummary(const FunctionDecl *FD, + bool &AllowAnnotations); + + /// Return a summary for OSObject, or nullptr if not found. + const RetainSummary *getSummaryForOSObject(const FunctionDecl *FD, + StringRef FName, QualType RetTy); + + /// Return a summary for Objective-C or CF object, or nullptr if not found. + const RetainSummary *getSummaryForObjCOrCFObject( + const FunctionDecl *FD, + StringRef FName, + QualType RetTy, + const FunctionType *FT, + bool &AllowAnnotations); + + /// Apply the annotation of {@code pd} in function {@code FD} + /// to the resulting summary stored in out-parameter {@code Template}. + /// \return whether an annotation was applied. + bool applyParamAnnotationEffect(const ParmVarDecl *pd, unsigned parm_idx, + const NamedDecl *FD, + RetainSummaryTemplate &Template); + +public: + RetainSummaryManager(ASTContext &ctx, + bool usesARC, + bool trackObjCAndCFObjects, + bool trackOSObjects) + : Ctx(ctx), + ARCEnabled(usesARC), + TrackObjCAndCFObjects(trackObjCAndCFObjects), + TrackOSObjects(trackOSObjects), + AF(BPAlloc), + ObjCAllocRetE(usesARC ? RetEffect::MakeNotOwned(ObjKind::ObjC) + : RetEffect::MakeOwned(ObjKind::ObjC)), + ObjCInitRetE(usesARC ? RetEffect::MakeNotOwned(ObjKind::ObjC) + : RetEffect::MakeOwnedWhenTrackedReceiver()) { + InitializeClassMethodSummaries(); + InitializeMethodSummaries(); + } + + enum class BehaviorSummary { + // Function does not return. + NoOp, + + // Function returns the first argument. + Identity, + + // Function either returns zero, or the input parameter. + IdentityOrZero + }; + + Optional<BehaviorSummary> canEval(const CallExpr *CE, const FunctionDecl *FD, + bool &hasTrustedImplementationAnnotation); + + bool isTrustedReferenceCountImplementation(const FunctionDecl *FD); + + const RetainSummary *getSummary(const CallEvent &Call, + QualType ReceiverType=QualType()); + + const RetainSummary *getFunctionSummary(const FunctionDecl *FD); + + const RetainSummary *getMethodSummary(Selector S, const ObjCInterfaceDecl *ID, + const ObjCMethodDecl *MD, + QualType RetTy, + ObjCMethodSummariesTy &CachedSummaries); + + const RetainSummary * + getInstanceMethodSummary(const ObjCMethodCall &M, + QualType ReceiverType); + + const RetainSummary *getClassMethodSummary(const ObjCMethodCall &M) { + assert(!M.isInstanceMessage()); + const ObjCInterfaceDecl *Class = M.getReceiverInterface(); + + return getMethodSummary(M.getSelector(), Class, M.getDecl(), + M.getResultType(), ObjCClassMethodSummaries); + } + + /// getMethodSummary - This version of getMethodSummary is used to query + /// the summary for the current method being analyzed. + const RetainSummary *getMethodSummary(const ObjCMethodDecl *MD) { + const ObjCInterfaceDecl *ID = MD->getClassInterface(); + Selector S = MD->getSelector(); + QualType ResultTy = MD->getReturnType(); + + ObjCMethodSummariesTy *CachedSummaries; + if (MD->isInstanceMethod()) + CachedSummaries = &ObjCMethodSummaries; + else + CachedSummaries = &ObjCClassMethodSummaries; + + return getMethodSummary(S, ID, MD, ResultTy, *CachedSummaries); + } + + const RetainSummary *getStandardMethodSummary(const ObjCMethodDecl *MD, + Selector S, QualType RetTy); + + /// Determine if there is a special return effect for this function or method. + Optional<RetEffect> getRetEffectFromAnnotations(QualType RetTy, + const Decl *D); + + void updateSummaryFromAnnotations(const RetainSummary *&Summ, + const ObjCMethodDecl *MD); + + void updateSummaryFromAnnotations(const RetainSummary *&Summ, + const FunctionDecl *FD); + + + void updateSummaryForCall(const RetainSummary *&Summ, + const CallEvent &Call); + + bool isARCEnabled() const { return ARCEnabled; } + + RetEffect getObjAllocRetEffect() const { return ObjCAllocRetE; } + + /// Determine whether a declaration {@code D} of correspondent type (return + /// type for functions/methods) {@code QT} has any of the given attributes, + /// provided they pass necessary validation checks AND tracking the given + /// attribute is enabled. + /// Returns the object kind corresponding to the present attribute, or None, + /// if none of the specified attributes are present. + /// Crashes if passed an attribute which is not explicitly handled. + template <class T> + Optional<ObjKind> hasAnyEnabledAttrOf(const Decl *D, QualType QT); + + template <class T1, class T2, class... Others> + Optional<ObjKind> hasAnyEnabledAttrOf(const Decl *D, QualType QT); + + friend class RetainSummaryTemplate; +}; + + +// Used to avoid allocating long-term (BPAlloc'd) memory for default retain +// summaries. If a function or method looks like it has a default summary, but +// it has annotations, the annotations are added to the stack-based template +// and then copied into managed memory. +class RetainSummaryTemplate { + RetainSummaryManager &Manager; + const RetainSummary *&RealSummary; + RetainSummary ScratchSummary; + bool Accessed; +public: + RetainSummaryTemplate(const RetainSummary *&real, RetainSummaryManager &mgr) + : Manager(mgr), RealSummary(real), ScratchSummary(*real), Accessed(false) {} + + ~RetainSummaryTemplate() { + if (Accessed) + RealSummary = Manager.getPersistentSummary(ScratchSummary); + } + + RetainSummary &operator*() { + Accessed = true; + return ScratchSummary; + } + + RetainSummary *operator->() { + Accessed = true; + return &ScratchSummary; + } +}; + +} // end namespace ento +} // end namespace clang + +#endif |