Index: docs/ClangCommandLineReference.rst =================================================================== --- docs/ClangCommandLineReference.rst +++ docs/ClangCommandLineReference.rst @@ -84,7 +84,7 @@ .. option:: --analyzer-output -Static analyzer report output format (html\|plist\|plist-multi-file\|plist-html\|text). +Static analyzer report output format (html\|plist\|plist-multi-file\|plist-html\|text|counterexample). .. option:: -ansi, --ansi Index: include/clang/Driver/Options.td =================================================================== --- include/clang/Driver/Options.td +++ include/clang/Driver/Options.td @@ -2293,7 +2293,7 @@ def _analyze_auto : Flag<["--"], "analyze-auto">, Flags<[DriverOption]>; def _analyzer_no_default_checks : Flag<["--"], "analyzer-no-default-checks">, Flags<[DriverOption]>; def _analyzer_output : JoinedOrSeparate<["--"], "analyzer-output">, Flags<[DriverOption]>, - HelpText<"Static analyzer report output format (html|plist|plist-multi-file|plist-html|text).">; + HelpText<"Static analyzer report output format (html|plist|plist-multi-file|plist-html|text|counterexample).">; def _analyze : Flag<["--"], "analyze">, Flags<[DriverOption, CoreOption]>, HelpText<"Run the static analyzer">; def _assemble : Flag<["--"], "assemble">, Alias; Index: include/clang/StaticAnalyzer/Core/Analyses.def =================================================================== --- include/clang/StaticAnalyzer/Core/Analyses.def +++ include/clang/StaticAnalyzer/Core/Analyses.def @@ -34,6 +34,8 @@ 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(TEXT, "text", "Text output of analysis results", createTextPathDiagnosticConsumer) +ANALYSIS_DIAGNOSTICS(COUNTEREXAMPLE, "counterexample", "Output counterexample information using HTML", createCounterexampleDiagnosticsConsumer) + #ifndef ANALYSIS_PURGE #define ANALYSIS_PURGE(NAME, CMDFLAG, DESC) Index: include/clang/StaticAnalyzer/Core/AnalyzerOptions.h =================================================================== --- include/clang/StaticAnalyzer/Core/AnalyzerOptions.h +++ include/clang/StaticAnalyzer/Core/AnalyzerOptions.h @@ -523,6 +523,9 @@ /// in the CFG. bool shouldConditionalizeStaticInitializers(); + /// \return true if counterexamples should be dumped to stderr. + bool shouldDumpCounterexample(); + // Returns the size of the functions (in basic blocks), which should be // considered to be small enough to always inline. // Index: include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h =================================================================== --- include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h +++ include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h @@ -365,6 +365,10 @@ bool IsArg = false, bool EnableNullFPSuppression = true); +/// \return visitor which performs counterexample printing. +/// TODO: it is not very nice that the type is hidden... +std::unique_ptr getCounterexamplePrinter(); + const Expr *getDerefExpr(const Stmt *S); const Stmt *GetDenomExpr(const ExplodedNode *N); const Stmt *GetRetValExpr(const ExplodedNode *N); Index: include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h =================================================================== --- include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h +++ include/clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h @@ -101,7 +101,13 @@ void HandlePathDiagnostic(std::unique_ptr D); - enum PathGenerationScheme { None, Minimal, Extensive, AlternateExtensive }; + enum PathGenerationScheme { + None, + Minimal, + Extensive, + AlternateExtensive, + CounterexampleDump + }; virtual PathGenerationScheme getGenerationScheme() const { return Minimal; } virtual bool supportsLogicalOpControlFlow() const { return false; } Index: lib/StaticAnalyzer/Core/AnalyzerOptions.cpp =================================================================== --- lib/StaticAnalyzer/Core/AnalyzerOptions.cpp +++ lib/StaticAnalyzer/Core/AnalyzerOptions.cpp @@ -368,6 +368,10 @@ return getBooleanOption("cfg-conditional-static-initializers", true); } +bool AnalyzerOptions::shouldDumpCounterexample() { + return getBooleanOption("dump-counterexample", false); +} + bool AnalyzerOptions::shouldInlineLambdas() { if (!InlineLambdas.hasValue()) InlineLambdas = getBooleanOption("inline-lambdas", /*Default=*/true); Index: lib/StaticAnalyzer/Core/BugReporter.cpp =================================================================== --- lib/StaticAnalyzer/Core/BugReporter.cpp +++ lib/StaticAnalyzer/Core/BugReporter.cpp @@ -527,6 +527,25 @@ return R->isValid(); } +/// Runs \c PrinterVisitor on the diagnostics. +/// Does not run any other visitors. +static bool GenerateCounterexampleDiagnostic(PathDiagnostic &PD, + PathDiagnosticBuilder &PDB, + const ExplodedNode *N) { + N = N->getFirstPred(); + if (!N) + return true; + + BugReport *R = PDB.getBugReport(); + auto V = bugreporter::getCounterexamplePrinter(); + + while (const ExplodedNode *Pred = N->getFirstPred()) { + std::shared_ptr Diag = V->VisitNode(N, Pred, PDB, *R); + N = Pred; + } + return R->isValid(); +} + //===----------------------------------------------------------------------===// // "Minimal" path diagnostic generation algorithm. //===----------------------------------------------------------------------===// @@ -3180,6 +3199,9 @@ case PathDiagnosticConsumer::None: GenerateVisitorsOnlyPathDiagnostic(PD, PDB, N, visitors); break; + case PathDiagnosticConsumer::CounterexampleDump: + GenerateCounterexampleDiagnostic(PD, PDB, N); + break; } // Clean up the visitors we used. Index: lib/StaticAnalyzer/Core/BugReporterVisitors.cpp =================================================================== --- lib/StaticAnalyzer/Core/BugReporterVisitors.cpp +++ lib/StaticAnalyzer/Core/BugReporterVisitors.cpp @@ -22,9 +22,12 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Support/raw_ostream.h" +#include +#include using namespace clang; using namespace ento; @@ -1878,3 +1881,144 @@ return std::move(Piece); } + +/// Export the counterexample to C. +class PrinterVisitor final : public BugReporterVisitorImpl { + + /// File ID followed by a line number. + llvm::SetVector> VisitedLines; + + /// Output stream to write into. + raw_ostream &Ostream; + + /// State machine variables. + mutable bool DonePrinting = false; + + /// Max number of chars used to display the filename. + static const unsigned MAX_FILENAME_MARGIN = 80; + static const unsigned MARGIN_SEP_LEN = 1; + static constexpr const char *const REPORT_SEPARATOR = + "/* ============================================================== */\n"; + +public: + PrinterVisitor(raw_ostream &Ostream) : Ostream(Ostream) {} + + PrinterVisitor() = delete; + + void Profile(llvm::FoldingSetNodeID &ID) const override { + static int Tag = 0; + ID.AddPointer(&Tag); + } + + std::shared_ptr VisitNode(const ExplodedNode *N, + const ExplodedNode *PrevN, + BugReporterContext &BRC, + BugReport &BR) override { + SourceManager &SM = BRC.getSourceManager(); + + if (DonePrinting) { // Printing was done, do nothing. + return nullptr; + } else if (!PrevN->getFirstPred()) { // Finished report, do printing. + + // Went through the entire bug report, now print the lines in reverse + // order. + bool Status = doPrinting(SM); + if (!Status) + Ostream << "Error while printing\n"; + Ostream << REPORT_SEPARATOR; + DonePrinting = true; + return nullptr; + } else if (const Stmt *S = PathDiagnosticLocation::getStmt(N)) { + SourceLocation Loc = S->getSourceRange().getBegin(); + VisitedLines.insert( + std::make_pair(SM.getFileID(Loc), SM.getSpellingLineNumber(Loc))); + } + return nullptr; + } + +private: + /// Print locations serialized to \c VisitedLines. + bool doPrinting(SourceManager &SM) { + unsigned Margin = calculateMargin(SM); + for (auto It = VisitedLines.rbegin(), ItEnd = VisitedLines.rend(); + It != ItEnd; ++It) { + FileID FID = It->first; + unsigned LineNo = It->second; + bool Status = printLine(SM, FID, LineNo, Margin); + if (!Status) + return false; + } + return true; + } + + /// Print line \p LineNo from file \p FID, with left margin \p Margin. + /// \return \c true on success, \c false on failure. + bool printLine(SourceManager &SM, FileID FID, unsigned LineNo, + unsigned Margin) { + SourceLocation Location = SM.translateLineCol(FID, LineNo, 1); + unsigned Offset = SM.getFileOffset(Location); + + // Print location first. + int Status = printLocation(SM, Location, Margin); + if (!Status) + return false; + + bool Invalid = false; + const char *BufferStart = SM.getBufferData(FID, &Invalid).data(); + if (Invalid) + return false; + + unsigned FileEndOffset = SM.getFileOffset(SM.getLocForEndOfFile(FID)); + for (unsigned i = Offset; BufferStart[i] != '\n' && i < FileEndOffset; ++i) + Ostream << BufferStart[i]; + + Ostream << "\n"; + return true; + } + + /// Print location in left margin. + bool printLocation(SourceManager &SM, SourceLocation Loc, unsigned Margin) { + Loc = SM.getExpansionLoc(Loc); + PresumedLoc PLoc = SM.getPresumedLoc(Loc); + if (PLoc.isInvalid()) + return false; + + uint64_t SavedPos = Ostream.tell(); + Ostream << PLoc.getFilename() << ":" << PLoc.getLine(); + uint64_t Delta = Ostream.tell() - SavedPos; + assert(Margin >= Delta); + for (unsigned i = Delta; i < Margin; i++) + Ostream << " "; + Ostream << "|"; + + return true; + } + + /// \return smallest margin required to fit all filenames present + /// in the counterexample. + unsigned calculateMargin(SourceManager &SM) { + unsigned Out = 0; + for (auto Pair : VisitedLines) { + FileID FID = Pair.first; + unsigned LineNo = Pair.second; + SourceLocation Loc = SM.translateLineCol(FID, LineNo, 1); + Loc = SM.getExpansionLoc(Loc); + PresumedLoc PLoc = SM.getPresumedLoc(Loc); + if (PLoc.isInvalid()) + continue; + + // Take logarithm to figure out number of chars required. + long LineMargin = 1 + std::lround(floor(log10(PLoc.getLine()))); + size_t FilenameMargin = strnlen(PLoc.getFilename(), MAX_FILENAME_MARGIN); + assert(LineMargin > 0); + unsigned RequiredMargin = FilenameMargin + LineMargin + MARGIN_SEP_LEN; + if (RequiredMargin > Out) + Out = RequiredMargin; + } + return Out; + } +}; + +std::unique_ptr bugreporter::getCounterexamplePrinter() { + return llvm::make_unique(llvm::errs()); +} Index: lib/StaticAnalyzer/Core/CMakeLists.txt =================================================================== --- lib/StaticAnalyzer/Core/CMakeLists.txt +++ lib/StaticAnalyzer/Core/CMakeLists.txt @@ -25,6 +25,7 @@ CommonBugCategories.cpp ConstraintManager.cpp CoreEngine.cpp + CounterexampleDiagnostics.cpp DynamicTypeMap.cpp Environment.cpp ExplodedGraph.cpp Index: lib/StaticAnalyzer/Core/CounterexampleDiagnostics.cpp =================================================================== --- /dev/null +++ lib/StaticAnalyzer/Core/CounterexampleDiagnostics.cpp @@ -0,0 +1,40 @@ +#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h" +#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h" +#include "clang/StaticAnalyzer/Core/PathDiagnosticConsumers.h" +#include "llvm/ADT/StringRef.h" + +using namespace clang; +using namespace ento; + +namespace { + +/// Dump the counterexample to stderr. +class CounterexampleDiagnostics : public PathDiagnosticConsumer { + +public: + CounterexampleDiagnostics() {} + + bool supportsCrossFileDiagnostics() const override { return false; } + + ~CounterexampleDiagnostics() override { FlushDiagnostics(nullptr); } + + StringRef getName() const override { return "CounterexampleDiagnostics"; } + + /// Force usage of the counterexample visitor. + PathGenerationScheme getGenerationScheme() const override { + return CounterexampleDump; + } + + void FlushDiagnosticsImpl(std::vector &Diags, + FilesMade *filesMade) override { + // FIXME move counterexample dumping logic here. + } +}; + +} // end anonymous namespace + +void ento::createCounterexampleDiagnosticsConsumer( + AnalyzerOptions &AnalyzerOpts, PathDiagnosticConsumers &C, + const std::string &prefix, const Preprocessor &PP) { + C.push_back(new CounterexampleDiagnostics()); +}