[clangd] Extend --check to time clang-tidy checks, so we can block slow ones

[sammccall]

Summary

misc-const-correctness is so catastrophically slow that we need to block it
from running. But we need a way to detect this without breaking users first.

This is part of a plan to run only fast checks by default.
More details in https://github.com/clangd/clangd/issues/1337

[kadircet]

thanks, lgtm!

clang-tools-extra/clangd/tool/Check.cpp

67

i guess we also need a llvm::cl::cat(Check) here?

302

nit: StringRef or std::string& or auto

[sammccall]

clang-tools-extra/clangd/tool/Check.cpp

67

Removed the category instead, it's useless afaict

clang-tools-extra/clangd/tool/Check.cpp

 // and then running features at many locations.
 //
 // Currently it adds some basic logging of progress and results.
 // We should consider extending it to also recognize common symptoms and
 // recommend solutions (e.g. standard library installation issues).
 //
 //===----------------------------------------------------------------------===//
 
+#include "../clang-tidy/ClangTidyModuleRegistry.h"
+#include "../clang-tidy/GlobList.h"
 #include "ClangdLSPServer.h"
 #include "CodeComplete.h"
 #include "CompileCommands.h"
 #include "Config.h"
+#include "Feature.h"
 #include "GlobalCompilationDatabase.h"
 #include "Hover.h"
 #include "InlayHints.h"
 #include "ParsedAST.h"
 #include "Preamble.h"
 #include "Protocol.h"
 #include "SemanticHighlighting.h"
 #include "SourceCode.h"
 #include "XRefs.h"
 #include "index/CanonicalIncludes.h"
 #include "index/FileIndex.h"
 #include "refactor/Tweak.h"
 #include "support/ThreadsafeFS.h"
 #include "support/Trace.h"
 #include "clang/AST/ASTContext.h"
+#include "clang/Basic/Diagnostic.h"
 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/Support/Path.h"
+#include "llvm/Support/Process.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
+// These will never be shown in --help, ClangdMain doesn't list the category.
+llvm::cl::opt<std::string> CheckTidyTime(
+    "check-tidy-time",
+    llvm::cl::desc("Print the overhead of checks matching this glob"),
+    llvm::cl::init(""));
+
 // Print (and count) the error-level diagnostics (warnings are ignored).
 unsigned showErrors(llvm::ArrayRef<Diag> Diags) {
   unsigned ErrCount = 0;
   for (const auto &D : Diags) {
     if (D.Severity >= DiagnosticsEngine::Error) {
       elog("[{0}] Line {1}: {2}", D.Name, D.Range.start.line + 1, D.Message);
       ++ErrCount;
     }
   }
   return ErrCount;
 }
 
+std::vector<std::string> listTidyChecks(llvm::StringRef Glob) {
+  tidy::GlobList G(Glob);
+  tidy::ClangTidyCheckFactories CTFactories;
+  for (const auto &E : tidy::ClangTidyModuleRegistry::entries())
+    E.instantiate()->addCheckFactories(CTFactories);
+  std::vector<std::string> Result;
+  for (const auto &E : CTFactories)
+    if (G.contains(E.getKey()))
+      Result.push_back(E.getKey().str());
+  llvm::sort(Result);
+  return Result;
+}
+
 // This class is just a linear pipeline whose functions get called in sequence.
 // Each exercises part of clangd's logic on our test file and logs results.
 // Later steps depend on state built in earlier ones (such as the AST).
 // Many steps can fatally fail (return false), then subsequent ones cannot run.
 // Nonfatal failures are logged and tracked in ErrCount.
 class Checker {
   // from constructor
   std::string File;
bool buildAST() {
     }
     ErrCount += showErrors(llvm::makeArrayRef(*AST->getDiagnostics())
                                .drop_front(Preamble->Diags.size()));
 
     if (Opts.BuildDynamicSymbolIndex) {
       log("Indexing AST...");
       Index.updateMain(File, *AST);
     }
+
+    if (!CheckTidyTime.empty()) {
+      if (!CLANGD_TIDY_CHECKS) {
+        elog("-{0} requires -DCLANGD_TIDY_CHECKS!", CheckTidyTime.ArgStr);
+        return false;
+      }
+      checkTidyTimes();
+    }
+
     return true;
   }
 
+  // For each check foo, we want to build with checks=-* and checks=-*,foo.
+  // (We do a full build rather than just AST matchers to meausre PPCallbacks).
+  //
+  // However, performance has both random noise and systematic changes, such as
+  // step-function slowdowns due to CPU scaling.
+  // We take the median of 5 measurements, and after every check discard the
+  // measurement if the baseline changed by >3%.
+  void checkTidyTimes() {
+    double Stability = 0.03;
+    log("Timing AST build with individual clang-tidy checks (target accuracy "
+        "{0:P0})",
+        Stability);
+
+    using Duration = std::chrono::nanoseconds;
+    // Measure time elapsed by a block of code. Currently: user CPU time.
+    auto Time = [&](auto &&Run) -> Duration {
+      llvm::sys::TimePoint<> Elapsed;
+      std::chrono::nanoseconds UserBegin, UserEnd, System;
+      llvm::sys::Process::GetTimeUsage(Elapsed, UserBegin, System);
+      Run();
+      llvm::sys::Process::GetTimeUsage(Elapsed, UserEnd, System);
+      return UserEnd - UserBegin;
+    };
+    auto Change = [&](Duration Exp, Duration Base) -> double {
+      return (double)(Exp.count() - Base.count()) / Base.count();
+    };
+    // Build ParsedAST with a fixed check glob, and return the time taken.
+    auto Build = [&](llvm::StringRef Checks) -> Duration {
+      TidyProvider CTProvider = [&](tidy::ClangTidyOptions &Opts,
+                                    llvm::StringRef) {
+        Opts.Checks = Checks.str();
+      };
+      Inputs.ClangTidyProvider = CTProvider;
+      // Sigh, can't reuse the CompilerInvocation.
+      IgnoringDiagConsumer IgnoreDiags;
+      auto Invocation = buildCompilerInvocation(Inputs, IgnoreDiags);
+      Duration Val = Time([&] {
+        ParsedAST::build(File, Inputs, std::move(Invocation), {}, Preamble);
+      });
+      vlog("    Measured {0} ==> {1}", Checks, Val);
+      return Val;
+    };
+    // Measure several times, return the median.
+    auto MedianTime = [&](llvm::StringRef Checks) -> Duration {
+      std::array<Duration, 5> Measurements;
+      for (auto &M : Measurements)
+        M = Build(Checks);
+      llvm::sort(Measurements);
+      return Measurements[Measurements.size() / 2];
+    };
+    Duration Baseline = MedianTime("-*");
+    log("  Baseline = {0}", Baseline);
+    // Attempt to time a check, may update Baseline if it is unstable.
+    auto Measure = [&](llvm::StringRef Check) -> double {
+      for (;;) {
+        Duration Median = MedianTime(("-*," + Check).str());
+        Duration NewBase = MedianTime("-*");
+
+        // Value only usable if baseline is fairly consistent before/after.
+        double DeltaFraction = Change(NewBase, Baseline);
+        Baseline = NewBase;
+        vlog("  Baseline = {0}", Baseline);
+        if (DeltaFraction < -Stability || DeltaFraction > Stability) {
+          elog("  Speed unstable, discarding measurement.");
+          continue;
+        }
+        return Change(Median, Baseline);
+      }
+    };
+
+    for (const auto& Check : listTidyChecks(CheckTidyTime)) {
+      // vlog the check name in case we crash!
+      vlog("  Timing {0}", Check);
+      double Fraction = Measure(Check);
+      log("  {0} = {1:P0}", Check, Fraction);
+    }
+    log("Finished individual clang-tidy checks");
+
+    // Restore old options.
+    Inputs.ClangTidyProvider = Opts.ClangTidyProvider;
+  }
+
   // Build Inlay Hints for the entire AST or the specified range
   void buildInlayHints(llvm::Optional<Range> LineRange) {
     log("Building inlay hints");
     auto Hints = inlayHints(*AST, LineRange);
 
     for (const auto &Hint : Hints) {
       vlog("  {0} {1} {2}", Hint.kind, Hint.position, Hint.label);
     }