Added a boolean option handle-integral-cast-for-ranges under -analyzer-config flag. Disabled the feature by default.

I appologize for my immaturity and for the audacity of my infantile assumptions. I admit any constructive criticism. Thank you for referencing the theory. I will thoroughly study the domain in all.

! In D103317#2793797, @vsavchenko wrote:

In D103317#2793797, @vsavchenko wrote:

Hmm, Okay, but what about situations if you have: a = a1 + a2 and a = a3 + a4 + a5 are you going to throw away one of these constraints? And if so, how do you want to select which one?

Are you talking about comparison or assignment? Both assignments can't be valid at the same time, and latter replaces bindings of former. In case of comparisons, they both can be valid.
But we should keep in mind that assignment is a write operation which replaces and invalidates previous bindings, and comparison a read operation. It can add new bindings but can not remove old ones.
This what I haven't dig deep enough yet. Let's do this together how we can handle that.

In D103317#2793658, @vsavchenko wrote:

But the problem it is generally not one-to-one relationship, so x -> y1 + 1, x -> y2 + 2, ... , x -> yN + N.

In my approach it can't be more then one binding for one symbol. Like:
x = y + z; produces $x = $y + $z, $y = $x - $z, $z = $x - $y.
Then if z = a;, all above should be invalidated (removed), because we can't rely on those expressions any more. And new ones should be added $z = $a and $a = $z.

As you can see, this is BRUTE FORCE.

I would say this is a linked list with stop-markers, not blindly passing through all the bindings. And I don't talk about implementation details. For now we just need to elaborate an approach.

Returning to the discussion raised in D102696, I'd like to share my vision.
I think we can use much easier approach to use valid constraints at any point of time.
The main idea is lazy-reasoning of the ranges.
This approach:

• doesn't need to use canonicalization;
• doesn't need to update all the constraints on each setConstraint call (using brute-force or any other structure traversals);
• add an additional bindings for every simple operand on each assignment or initialization.
• remove an invalid bindings for every simple operand on each assignment or initialization.
• recursively get the range when and only when needed (lazy-reasoning).

@NoQ
This solution only intends to make correct calculations whenever cast occures. We can mark this as alpha or add an argument flag to turn cast reasoning on/off, or we can even disable any part of this patch with argument settings.

But this still requires massive testing, a lot more than a typical constraint solver patch; extraordinary claims require extraordinary evidence.

What kind of tests do you think we need?

If it works out though, it might be the best thing to happen to the static analyzer in years.

Thank you. I appreciate your possitive evaluation.

With SymbolCasts in place our equations become much more complicated and therefore the constraint solver becomes much more likely to produce false positives in cases where it previously erred on the side of false negatives.

Another thing to test is our ability to explain bug paths.

My proposition is to design and describe a paper of:

• what cases shall be considered as erroneous and be reported;
• what cases shall be ignored or considered as exceptions (i.e. static_cast);
• what wordings shall we use in reports;
• how paths of those reports shall look like;
• your options;

But in practice there may be other reasons to use a larger integer type, such as API requirements (eg., how isascii() accepts an int but only uses 266 values).

IMO this is great when we tell user that he/she should make sure of the value bounds before passing the arguments to such APIs.

There's also the usual problem of overflow being impossible specifically on the current path; in this case we have to make sure that an appropriate assert() would actually suppress the warning (i.e., the constraint solver would be able to correctly solve the assert condition as well).

For example, this test easily passes.

void test(int x) {
  assert(0 < x && x < 42);
  char c = x;
  clang_analyzer_eval(c <= 0); // expected-warning {{FALSE}}
  clang_analyzer_eval(c >= 42); // expected-warning {{FALSE}}
}

Or you meant some other cases?

__
*In this case it's interesting as a control flow dependency of the bug location; it sounds like without @Szelethus's control flow dependency tracking this advancement would have been virtually impossible.

Can this tracking mechanism be adjusted then?

@NoQ

I guess another option is to put loc::MemRegionVal() inside castRegion(). This way the return type Optional<loc::MemRegionVal> unambigously tells that the region is always non-null if present (protected by the assertion in the constructor of loc::MemRegionVal).

Fixed syntax complains which caused a test fail.

Added a simplified test case.

@steakhal, @NoQ
Thanks for your replies. I've made a patch according your suggestions D103319.

OK, then. Let's land it!

@vsavchenko How about this?

Fixed the issue. Added more unit tests.

Mistakenly erased with another patch. Restored. But anyway this revision should be abandoned as irrelevant any more.

@vsavchenko
Reworked the algorithm.

@vsavchenko
Thanks for your suggestions! I really appreciate it! I'll do my best on this algorithm.

More minor improvements in unit tests.

Minor improvements in unit tests.

Reworked the solution. Returned to Implemented two versions of the same algorithm. Most optimized (but more verbose) and generalized one (but less optimized).
Added a bit more tests. @vsavchenko , please, look.

@vsavchenko Thanka for the suggestions! I'll take them into account and update the patch.

Minor performance improvement. Add more comments.

Minor comment fix.

Updated the patch due to comments. Added more tests. Simplified and improved solution.

@vabridgers
Thank you for a good catch! The fix looks fairly reasonable for me!

In D92639#2717134, @vsavchenko wrote:

In D92639#2716973, @ASDenysPetrov wrote:

@vsavchenko
I make some tests and fixes. Please, consider.

OMG, that's so awesome! Thank you so much!

@NoQ, @steakhal, @vsavchenko
I think we have met all the conditions with previous patchs to make this patch acceptable.
If you think it's OK, could you, please, approve it?

@vsavchenko
I made some tests and fixed. Please, consider.

This is the only revision in the stack which was bypass your attention. It's fairly harmless although a big one. Please, look at it.

Already approved a month ago D97277 :-) That's the next step.

In addition to the above:

@NoQ

Even though NFC commits don't require tests, this doesn't mean they shouldn't add them!

While developing this, I wasn't able to reproduce any regression or unpassed cases on the projects from CodeChecker list (Bitcoin_v0.20.1, Curl_curl-7_66_0, Memchached_1.6.8, OpenSSL_openssl-3.0.0-alpha7, etc.) due to my platform. I use Windows and those projects either don't compile or need hard effort to set them up.
But anyway I was able to detect some different diagnostics in existing tests casts.cpp using Z3 refutation option. That actually helped to make corrections.

@NoQ
Many thanks for your evaluation!

@vsavchenko
Thank you for the proposed solution. It looks much easier to understand and maintain. Great! I will take it into account.

Well, that is a nice exercise for "two pointer" problems, but can we please talk about the actual use case for it?

I'm currently working on integral cast between ranges. Consider the range of int which is casted to char. You've got some ranges of int which obviously should be corespondently represented as some other ranges of char.
Some examples:

int [257, 259]  -> char [1, 3]
int [510, 513]  -> char [-2, 1]
int [42, 1000]  -> char [-128, 127]
int [257, 259] U [2049, 2051]  -> char [1,3] // Here we need `unite` logic to get the casted range because both original ranges lay on the same area after trancation.

Updated. Implemented four separate functions RangeSet::Factory::unite. Each function has the most optimized approach to handle intersections for the particular case.

@vsavchenko Many thanks for your feedback!
I will make a new separate function for checking intersections considering all your suggestions along with the old quick add versions. It'll be more optimized.

@steakhal thanks for the approval.

@vsavchenko FYI.

Updated. Restored complexity to O(N).

@vsavchenko
OK, what do you think of *adjacency* feature? I mean it simplifies such ranges [1,2][3,4][5,6] to [1,6]. Is it worth for implementation?

In D99797#2666358, @vsavchenko wrote:

Thanks for working on improvements of the solver and constraints! However, I have some tough questions about this patch.

What I really want to understand here is motivation. Why do we need to have add operation semantics like this in the first place? My guess is that "the user" will be in the following patch.
Additionally, I don't really like the idea of replacing something simple and fast (old add methods`) with something more complex unconditionally. Old users still don't need this additional logic. C++ has always been the language where we "pay for what we use".
So, with good motivation, I'd still prefer methods like add and addUnchecked or smith similar.

My motivation is that I'm currently working on some bigger improvement (symbolic integral cast) and stucked here of the lack of handling intersections. Would you mind of accepting this revision in case if I restore complexity to O(N+M)?

In D95246#2606343, @abhina.sreeskantharajan wrote:

This issue has been fixed in https://reviews.llvm.org/D97472.
@ASDenysPetrov I'm unable to close this revision and the other one https://reviews.llvm.org/D95808. Do you know what the appropriate action is here? To abandon this, or accept it again and close it?

In D95808#2657744, @jhenderson wrote:

@ASDenysPetrov, I think you need to mark this patch as Accepted so that someone can close this review.

In D98405#2639463, @nielx wrote:

Adding reviewer ASDenysPetrov (you recently reviewed some other work on this tool)

Sorry, I have to refuse your invitation. I have no competence in this. I was a reviewer for other revisions just because I've accidentally discovered fails of several tests on my environment (Windows+GCC+MSYS2), found a causer and raised an issue. I was just testing those patches using my specific environment and giving feedbacks, but not verifing the correctness.

Just a ping for you, guys, to let me move in this direction.

I'll check the patch a bit later on my Env.

Hi, @balazske

Updated.

In D96090#2618410, @NoQ wrote:

In all cases we're supposed to have an original type, whether we need it or not. Simply because we're simulating a typed language. If we don't have it it's a bug.

I agree. That's how evalCastFromNonLoc and evalCastFromLoc work now. Finally I want to replace them along with passing a correct original type. This is just one another step closer to this direction. I don't want patches be too complicated.

In D97388#2615104, @NoQ wrote:

Ok then, let's try to land it! 🤞

In D96090#2616666, @steakhal wrote:

You could still pass a default constructed QualType at each callsite.

We can try. At least it will be like this is a hack for the particular cases then, that will emphasis to pay attention to. Well, I'll present this version tomorrow.

I've checked this change. It works on my configuration at least.

In D97335#2614508, @sgraenitz wrote:

@ASDenysPetrov I guess you set the Needs Revision status accidentally?

Right. Probably the action was choosed previously in the drop-down list and I missed it. Sorry.

Updated due to discussion.

I'm not an expert in this field but this patch fixes my issue with the build on Windows.

In D97335#2611171, @sgraenitz wrote:

Does it fix the issue for you too?

Hi, Stefan. Thanks. I've checked. Yes, this fix (rGe984c2b06f0c59265ba2172bbdb2811c72123701) works for me.

@NoQ wrote:

IIUC this is roughly the first time ever when SValBuilder starts emitting symbols of float type. This is a huge change with an almost unlimited scope of unexpected side effects and very rigorous testing is required to understand the actual effect of this patch on programs that use floats. I think that generally some symbols are always better than no symbols, even if the constraint manager is completely unable to handle them. But we have to make sure that the entirety of SValBuilder and the entirety of RegionStore (and possibly the entirety of ExprEngine) are ready to deal with completely new kinds of values that they've never seen before.

I kind of abandoned this patch. I realized that too much circumstances appeared that I am not an expert in. It is more like an experimental patch which serves to make clear some information, raise a discussion of what another people know about handling floats. Thank you for your sharing. Now I see what potential problems could be. I'm going to proceed as soon as I feel more confident answering these questions.

@NoQ Thanks for your comment.

@NoQ
Thanks, I could finally draw your attention :)

Missed to add changes in unittests. Fixed.

My build fails after this patch. Could you revise your solution?
I'm using Win10, GCC+ninja
Here is my build output:

[32/92] Linking CXX executable bin\llvm-jitlink.exe
FAILED: bin/llvm-jitlink.exe
cmd.exe /C "cd . && D:\WORK\Utilities\MSYS2\mingw64\bin\c++.exe -Wa,-mbig-obj -Werror=date-time -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wno-missing-field-initializers -pedantic -Wno-long-long -Wimplicit-fallthrough -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-noexcept-type -Wdelete-non-virtual-dtor -Wsuggest-override -Wno-comment  -O2 -Wl,--stack,16777216    /export:llvm_orc_registerJITLoaderGDBWrapper tools/llvm-jitlink/CMakeFiles/llvm-jitlink.dir/llvm-jitlink.cpp.obj tools/llvm-jitlink/CMakeFiles/llvm-jitlink.dir/llvm-jitlink-elf.cpp.obj tools/llvm-jitlink/CMakeFiles/llvm-jitlink.dir/llvm-jitlink-macho.cpp.obj -o bin\llvm-jitlink.exe -Wl,--out-implib,lib\libllvm-jitlink.dll.a -Wl,--major-image-version,0,--minor-image-version,0  lib/libLLVMX86Desc.a  lib/libLLVMX86Disassembler.a  lib/libLLVMX86Info.a  lib/libLLVMBinaryFormat.a  lib/libLLVMExecutionEngine.a  lib/libLLVMJITLink.a  lib/libLLVMMC.a  lib/libLLVMObject.a  lib/libLLVMOrcJIT.a  lib/libLLVMOrcShared.a  lib/libLLVMOrcTargetProcess.a  lib/libLLVMRuntimeDyld.a  lib/libLLVMSupport.a  lib/libLLVMMCDisassembler.a  lib/libLLVMExecutionEngine.a  lib/libLLVMJITLink.a  lib/libLLVMOrcTargetProcess.a  lib/libLLVMOrcShared.a  lib/libLLVMRuntimeDyld.a  lib/libLLVMPasses.a  lib/libLLVMTarget.a  lib/libLLVMCoroutines.a  lib/libLLVMipo.a  lib/libLLVMBitWriter.a  lib/libLLVMFrontendOpenMP.a  lib/libLLVMIRReader.a  lib/libLLVMAsmParser.a  lib/libLLVMLinker.a  lib/libLLVMObjCARCOpts.a  lib/libLLVMScalarOpts.a  lib/libLLVMAggressiveInstCombine.a  lib/libLLVMInstCombine.a  lib/libLLVMVectorize.a  lib/libLLVMInstrumentation.a  lib/libLLVMTransformUtils.a  lib/libLLVMAnalysis.a  lib/libLLVMObject.a  lib/libLLVMBitReader.a  lib/libLLVMMCParser.a  lib/libLLVMMC.a  lib/libLLVMDebugInfoCodeView.a  lib/libLLVMDebugInfoMSF.a  lib/libLLVMTextAPI.a  lib/libLLVMProfileData.a  lib/libLLVMCore.a  lib/libLLVMBinaryFormat.a  lib/libLLVMRemarks.a  lib/libLLVMBitstreamReader.a  lib/libLLVMSupport.a  -lpsapi  -lshell32  -lole32  -luuid  -ladvapi32  D:/WORK/Utilities/MSYS2/mingw64/lib/libz.dll.a  lib/libLLVMDemangle.a  -lkernel32 -luser32 -lgdi32 -lwinspool -lshell32 -lole32 -loleaut32 -luuid -lcomdlg32 -ladvapi32 && cd ."
c++.exe: error: /export:llvm_orc_registerJITLoaderGDBWrapper: No such file or directory
[47/92] Linking CXX executable bin\clang-check.exe
ninja: build stopped: subcommand failed.

Here is my setup output if you're wondering cmake -GNinja ../llvm -DLLVM_LIT_ARGS=-sv -DLLVM_ENABLE_PROJECTS=clang -DLLVM_TARGETS_TO_BUILD=X86 -DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX=../../install -DLLVM_ENABLE_ASSERTIONS=ON:

My build fails after hack to this patch https://reviews.llvm.org/rG900f076113302e26e1939541b546b0075e3e9721. Could you revise your solution?
I'm using Win10, GCC+ninja
Here is my build output:

[32/92] Linking CXX executable bin\llvm-jitlink.exe
FAILED: bin/llvm-jitlink.exe
cmd.exe /C "cd . && D:\WORK\Utilities\MSYS2\mingw64\bin\c++.exe -Wa,-mbig-obj -Werror=date-time -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wno-missing-field-initializers -pedantic -Wno-long-long -Wimplicit-fallthrough -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-noexcept-type -Wdelete-non-virtual-dtor -Wsuggest-override -Wno-comment  -O2 -Wl,--stack,16777216    /export:llvm_orc_registerJITLoaderGDBWrapper tools/llvm-jitlink/CMakeFiles/llvm-jitlink.dir/llvm-jitlink.cpp.obj tools/llvm-jitlink/CMakeFiles/llvm-jitlink.dir/llvm-jitlink-elf.cpp.obj tools/llvm-jitlink/CMakeFiles/llvm-jitlink.dir/llvm-jitlink-macho.cpp.obj -o bin\llvm-jitlink.exe -Wl,--out-implib,lib\libllvm-jitlink.dll.a -Wl,--major-image-version,0,--minor-image-version,0  lib/libLLVMX86Desc.a  lib/libLLVMX86Disassembler.a  lib/libLLVMX86Info.a  lib/libLLVMBinaryFormat.a  lib/libLLVMExecutionEngine.a  lib/libLLVMJITLink.a  lib/libLLVMMC.a  lib/libLLVMObject.a  lib/libLLVMOrcJIT.a  lib/libLLVMOrcShared.a  lib/libLLVMOrcTargetProcess.a  lib/libLLVMRuntimeDyld.a  lib/libLLVMSupport.a  lib/libLLVMMCDisassembler.a  lib/libLLVMExecutionEngine.a  lib/libLLVMJITLink.a  lib/libLLVMOrcTargetProcess.a  lib/libLLVMOrcShared.a  lib/libLLVMRuntimeDyld.a  lib/libLLVMPasses.a  lib/libLLVMTarget.a  lib/libLLVMCoroutines.a  lib/libLLVMipo.a  lib/libLLVMBitWriter.a  lib/libLLVMFrontendOpenMP.a  lib/libLLVMIRReader.a  lib/libLLVMAsmParser.a  lib/libLLVMLinker.a  lib/libLLVMObjCARCOpts.a  lib/libLLVMScalarOpts.a  lib/libLLVMAggressiveInstCombine.a  lib/libLLVMInstCombine.a  lib/libLLVMVectorize.a  lib/libLLVMInstrumentation.a  lib/libLLVMTransformUtils.a  lib/libLLVMAnalysis.a  lib/libLLVMObject.a  lib/libLLVMBitReader.a  lib/libLLVMMCParser.a  lib/libLLVMMC.a  lib/libLLVMDebugInfoCodeView.a  lib/libLLVMDebugInfoMSF.a  lib/libLLVMTextAPI.a  lib/libLLVMProfileData.a  lib/libLLVMCore.a  lib/libLLVMBinaryFormat.a  lib/libLLVMRemarks.a  lib/libLLVMBitstreamReader.a  lib/libLLVMSupport.a  -lpsapi  -lshell32  -lole32  -luuid  -ladvapi32  D:/WORK/Utilities/MSYS2/mingw64/lib/libz.dll.a  lib/libLLVMDemangle.a  -lkernel32 -luser32 -lgdi32 -lwinspool -lshell32 -lole32 -loleaut32 -luuid -lcomdlg32 -ladvapi32 && cd ."
c++.exe: error: /export:llvm_orc_registerJITLoaderGDBWrapper: No such file or directory
[47/92] Linking CXX executable bin\clang-check.exe
ninja: build stopped: subcommand failed.

Here is my setup output if you're wondering cmake -GNinja ../llvm -DLLVM_LIT_ARGS=-sv -DLLVM_ENABLE_PROJECTS=clang -DLLVM_TARGETS_TO_BUILD=X86 -DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX=../../install -DLLVM_ENABLE_ASSERTIONS=ON:

Rebased on main.

Rebased on main.

Rebased on main.

Rebased on main.

Rebased on main.

LGTM. Let it be the most balanced solution.