clang-tidy with bugprone-unchecked-optional-access freezes on CDDA codebase

[andrei8l]

Clang-Tidy freezes on certain files of a large C++17 project.

Reproduction steps:
1.git clone --depth 1 https://github.com/CleverRaven/Cataclysm-DDA.git cdda
2.cmake -DCMAKE_EXPORT_COMPILE_COMMANDS=ON -S cdda -B build
3.clang-tidy -p build cdda/src/monstergenerator.cpp
=> clang-tidy freezes

If I add -bugprone-unchecked-optional-access, to .clang-tidy the problem goes away and Clang-Tidy finishes in ~2 minutes.

GDB backtrace for Clang-Tidy 16, sampled after ~20 minutes

Thread 1 (Thread 0x7ff72cc3d280 (LWP 954311) "clang-tidy"):
#0  0x0000557ab812b814 in clang::dataflow::WatchedLiteralsSolverImpl::solve() && ()
#1  0x0000557ab812af7e in clang::dataflow::WatchedLiteralsSolver::solve(llvm::DenseSet<clang::dataflow::BoolValue*, llvm::DenseMapInfo<clang::dataflow::BoolValue*, void> >) ()
#2  0x0000557ab811a1ad in clang::dataflow::DataflowAnalysisContext::querySolver(llvm::DenseSet<clang::dataflow::BoolValue*, llvm::DenseMapInfo<clang::dataflow::BoolValue*, void> >) ()
#3  0x0000557ab811a400 in clang::dataflow::DataflowAnalysisContext::flowConditionImplies(clang::dataflow::AtomicBoolValue&, clang::dataflow::BoolValue&) ()
#4  0x0000557ab810c9fc in clang::dataflow::UncheckedOptionalAccessModel::merge(clang::QualType, clang::dataflow::Value const&, clang::dataflow::Environment const&, clang::dataflow::Value const&, clang::dataflow::Environment const&, clang::dataflow::Value&, clang::dataflow::Environment&) ()
#5  0x0000557ab8122ae8 in clang::dataflow::Environment::join(clang::dataflow::Environment const&, clang::dataflow::Environment::ValueModel&) ()
#6  0x0000557ab81268d2 in clang::dataflow::transferCFGBlock(clang::CFGBlock const&, clang::dataflow::AnalysisContext&, std::function<void (clang::CFGElement const&, clang::dataflow::TypeErasedDataflowAnalysisState const&)>) ()
#7  0x0000557ab81273f0 in clang::dataflow::runTypeErasedDataflowAnalysis(clang::dataflow::ControlFlowContext const&, clang::dataflow::TypeErasedDataflowAnalysis&, clang::dataflow::Environment const&, std::function<void (clang::CFGElement const&, clang::dataflow::TypeErasedDataflowAnalysisState const&)>) ()
#8  0x0000557ab75f068c in llvm::Expected<std::vector<std::optional<clang::dataflow::DataflowAnalysisState<clang::dataflow::UncheckedOptionalAccessModel::Lattice> >, std::allocator<std::optional<clang::dataflow::DataflowAnalysisState<clang::dataflow::UncheckedOptionalAccessModel::Lattice> > > > > clang::dataflow::runDataflowAnalysis<clang::dataflow::UncheckedOptionalAccessModel>(clang::dataflow::ControlFlowContext const&, clang::dataflow::UncheckedOptionalAccessModel&, clang::dataflow::Environment const&, std::function<void (clang::CFGElement const&, clang::dataflow::DataflowAnalysisState<clang::dataflow::UncheckedOptionalAccessModel::Lattice> const&)>) ()
#9  0x0000557ab75f00e0 in clang::tidy::bugprone::UncheckedOptionalAccessCheck::check(clang::ast_matchers::MatchFinder::MatchResult const&) ()
#10 0x0000557ab952e20d in clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::MatchVisitor::visitMatch(clang::ast_matchers::BoundNodes const&) ()
#11 0x0000557ab955ba5c in clang::ast_matchers::internal::BoundNodesTreeBuilder::visitMatches(clang::ast_matchers::internal::BoundNodesTreeBuilder::Visitor*) ()
#12 0x0000557ab952dc2e in clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::matchWithFilter(clang::DynTypedNode const&) ()
#13 0x0000557ab9530510 in clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::TraverseDecl(clang::Decl*) ()
#14 0x0000557ab9538a5b in clang::RecursiveASTVisitor<clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor>::TraverseTranslationUnitDecl(clang::TranslationUnitDecl*) ()
#15 0x0000557ab9530d0c in clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::TraverseDecl(clang::Decl*) ()
#16 0x0000557ab9504ccb in clang::ast_matchers::MatchFinder::matchAST(clang::ASTContext&) ()
#17 0x0000557ab87aa91c in clang::MultiplexConsumer::HandleTranslationUnit(clang::ASTContext&) ()
#18 0x0000557ab89c9ebd in clang::ParseAST(clang::Sema&, bool, bool) ()
#19 0x0000557ab8772427 in clang::FrontendAction::Execute() ()
#20 0x0000557ab86ea094 in clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) ()
#21 0x0000557ab8189193 in clang::tooling::FrontendActionFactory::runInvocation(std::shared_ptr<clang::CompilerInvocation>, clang::FileManager*, std::shared_ptr<clang::PCHContainerOperations>, clang::DiagnosticConsumer*) ()
#22 0x0000557ab8153fd4 in clang::tidy::runClangTidy(clang::tidy::ClangTidyContext&, clang::tooling::CompilationDatabase const&, llvm::ArrayRef<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, llvm::IntrusiveRefCntPtr<llvm::vfs::OverlayFileSystem>, bool, bool, llvm::StringRef)::ActionFactory::runInvocation(std::shared_ptr<clang::CompilerInvocation>, clang::FileManager*, std::shared_ptr<clang::PCHContainerOperations>, clang::DiagnosticConsumer*) ()
#23 0x0000557ab8188ee6 in clang::tooling::ToolInvocation::runInvocation(char const*, clang::driver::Compilation*, std::shared_ptr<clang::CompilerInvocation>, std::shared_ptr<clang::PCHContainerOperations>) ()
#24 0x0000557ab8187e4b in clang::tooling::ToolInvocation::run() ()
#25 0x0000557ab818aa7a in clang::tooling::ClangTool::run(clang::tooling::ToolAction*) ()
#26 0x0000557ab814eef1 in clang::tidy::runClangTidy(clang::tidy::ClangTidyContext&, clang::tooling::CompilationDatabase const&, llvm::ArrayRef<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, llvm::IntrusiveRefCntPtr<llvm::vfs::OverlayFileSystem>, bool, bool, llvm::StringRef) ()
#27 0x0000557ab746e199 in clang::tidy::clangTidyMain(int, char const**) ()
#28 0x00007ff72c83c790 in __libc_start_call_main (main=main@entry=0x557ab7469900 <main>, argc=argc@entry=4, argv=argv@entry=0x7fff9b573488) at ../sysdeps/nptl/libc_start_call_main.h:58
#29 0x00007ff72c83c84a in __libc_start_main_impl (main=0x557ab7469900 <main>, argc=4, argv=0x7fff9b573488, init=<optimized out>, fini=<optimized out>, rtld_fini=<optimized out>, stack_end=0x7fff9b573478) at ../csu/libc-start.c:360
#30 0x0000557ab746981a in _start ()

Tried it with Clang-Tidy 15 from my distro

$ clang-tidy --version
LLVM (http://llvm.org/):
  LLVM version 15.0.7
  Optimized build.
  Default target: x86_64-pc-linux-gnu
  Host CPU: znver3

and Clang-Tidy 16 from this release

$ ~/clang16/bin/clang-tidy --version
LLVM (http://llvm.org/):
  LLVM version 16.0.0
  Optimized build.

Operating system:

DISTRIB_ID="Arch"
DISTRIB_RELEASE="rolling"
DISTRIB_DESCRIPTION="Arch Linux"

Also tried it in a Fedora 38 VM

[llvmbot]

@llvm/issue-subscribers-clang-tidy

[BrettDong]

It's likely a duplicate of #55530.

[andrei8l]

Fixed in LLVM 17. Thanks!