An alternative approach is to maintain separate counters for back edges and bail if those reach a certain limit. But this global limit is way simpler, so it looks good to me.

I prefer references to annotations, but this is also a step in the right direction :l

In D125931#3527584, @ymandel wrote:

1. In this patch, we go with a widening operation, but put the relevant logic in the core, so it can be reused for booleans in general.

Actually, I think in most cases we want to consistent how to merge bool values. So I wonder whether instead of reimplementing the merge operation in this check we should just call a function that does the work. And the same function should be used within the engine to merge states after if statements and so on.

While not having tests might be OK, but I'd prefer to introduce at least a couple uses of the new facilities so existing tests cover them.

Overall looks good to me. I wish some parts would be simpler but it looks like sometimes it is not easy to extend the current code and we might need to do some refactoring at some point.

Thanks, this looks good to me!

This approach fixes the worklist for the second phase. Would it be possible to create a wrapper that reverses the order of any worklist instead of committing to one and hardcode that?

In D121120#3496597, @ymandel wrote:

Just realized we left this open. How about a disclaimer at the top of the doc (.rst) file noting the potential cost? Anyone using clang-tidy should be explicitly configuring which checks to run, so that may be sufficient. If we want to allow users to enable/disable flow-sensitive checks across the board, though, it seems like we would need to add a new option to ClangTidyOptions (https://github.com/llvm/llvm-project/blob/main/clang-tools-extra/clang-tidy/ClangTidyOptions.h#L50).

It looks like all of my comments are resolved now, thanks!

Overall this looks good to me. However, I think this might not use the full potential of the check itself. With the information that the dataflow framework have it could distinguish between potentially unsafe accesses and provably unsafe accesses depending on whether the has_value property is constrained to be false. From the user point of view, it would be nice to emit different warning messages for the above two cases. This can help to gradually introduce this check to a larger codebase and focus on the higher severity diagnostics first.

Most checks in Clang Tidy will run relatively quickly as they usually can do most/all of their work in a single traversal. I wonder whether flow sensitive checks will prove to be a bit slower. I think adding slower checks to Tidy is fine, but it would be nice to properly set the expectations to the user (e.g. if an IDE is running Tidy in the background it might want to opt out from flow sensitive checks if they turn out to be slow). In case the performance is good, I think it should be fine as is. Otherwise I wonder if we want to add something like a tag to mark flow sensitive checks and give an option to turn them off.

Thanks for the clarifications!

The code looks good to me too. I was also wondering what sort of check will need this info.

Overall looks good to me. I am curious what will the strategy be to properly support construction. Do you plan to introduce a customization point to Env.createValue to give checks/models a way to set properties up? Or do you have something else in mind?

Nice! Did you do some measurements? Does this improve the performance or decrease the memory consumption?

> Make CTU a two phase analysis

In D123586#3449256, @ymandel wrote:

In D123586#3446956, @xazax.hun wrote:

Yeah, this is a hard problem in general. This looks like a sensible workaround for the short term, but I'm looking forward to a better solution. I'm a bit worried that the memory model will need some upgrades to properly solve this problem.

Thanks for the quick review! Yes, I have my concerns as well. It seems like some amount of a) additional allocation stabilization/memoization, b) introduction of explicit widening operator and c) structural comparison will fully solve the problem. Solving this properly is a high priority.

Yeah, this is a hard problem in general. This looks like a sensible workaround for the short term, but I'm looking forward to a better solution. I'm a bit worried that the memory model will need some upgrades to properly solve this problem.

The changes look good to me but please wait at least one more reviewer before committing.

Adding some reviewers

Speaking of builtins, it might be great to add tests for __builtin_unreachable, __builtin_trap, __builtin_debugtrap. The CFG might already have the right shape so we might not need to add any code to support them. But it would be nice to know :) Maybe we could even add a comment to VisitCallExpr why those wouldn't need explicit support.

Wow. This did take some iterations and I feel like I just added to the confusion at some point :D But the latest iteration looks much simpler and I'm confident it is right this time. Thanks!

In D122143#3396695, @ymandel wrote:

So, do you mean to add a FIXME to move to allowlist, or do you mean to hold off until we've switched? I have a short-term interest in getting this through for a particular usecase, but I understand if you feel it just not a good idea. Regardless, I'm going to get started exploring an allowlist approach.

Thanks! Did you have a chance whether this makes a difference in real world scenarios? I'm mostly curious because I do not have a good mental model of how the matchers are implemented, specifically what optimizations are in place, so I don't really know how much of an impact can caching make :)

Are smart pointers special? I would expect to see similar problems with containers (or even a nested optional). I wonder whether an allowlist instead of a denylist approach is better here. E.g., instead of disabling the modeling for smart pointers, we could enable it for cases that we actually support (or alternatively, we could add a confidence value to the unsafe access). Usually, these checks are pretty robust when we deal with objects on the stack of the analyzed function (locals, parameters), but it is really hard to reason about objects from the outside (e.g., when a reference to an object is acquired from a container or smart pointer) unless we have explicit modeling for the APIs. The confidence approach might be useful as we are unlikely to cover all the custom smart pointers the users have.

Thanks!

In D121694#3382587, @ymandel wrote:

In D121694#3382473, @xazax.hun wrote:

The change itself looks good. But out of curiosity, could you give me an example when we do not want to use the builtin transfer functions?

Sure! Pretty much any plain-vanilla dataflow analysis that sticks to its own lattice and doesn't care about the environment. The demo constant-propagation analyses are like this, but we have additional real analyses using the framework in this way. Examples include an analysis to detect raw pointers that could be unique pointers and one that detects missed opportunies to use std::move.

The change itself looks good. But out of curiosity, could you give me an example when we do not want to use the builtin transfer functions?

Thanks!

In D120992#3368118, @NoQ wrote:

I guess there's the usual direction that I occasionally suggest: develop a way to verify that all possible paths were explored during symbolic execution (CoreEngine::hasWorkRemaining() on steroids), then do most of the work in checkEndAnalysis.

Wonderful, thanks!

When pre-initializing fields in the environment, the code assumed that all fields of a struct would be initialized