This is an archive of the discontinued LLVM Phabricator instance.

[analyzer] Improved RangeSet::Negate support of unsigned ranges
ClosedPublic

Authored by ASDenysPetrov on Apr 9 2020, 7:10 AM.

Details

Summary

This fixes https://bugs.llvm.org/show_bug.cgi?id=41588
RangeSet Negate function shall handle unsigned ranges as well as signed ones.
RangeSet getRangeForMinusSymbol function shall use wider variety of ranges, not only concrete value ranges.
RangeSet Intersect functions shall not produce assertions.

Changes:
Improved safety of RangeSet::Intersect function. Added isEmpty() check to prevent an assertion.
Added support of handling unsigned ranges to RangeSet::Negate and RangeSet::getRangeForMinusSymbol.
Extended RangeSet::getRangeForMinusSymbol to return not only range sets with single value [n,n], but with wide ranges [n,m].
Added unit test for Negate function.
Added regression tests for unsigned values.

Diff Detail

Event Timeline

ASDenysPetrov created this revision.Apr 9 2020, 7:10 AM

It took me some time to understand what you were doing.
Probably a bit ASCII-art would have had help (eg. about the wrapping behavior).

By the same token, I wouldn't mind more tests, especially exercising the implemented behavior.
Probably unit-tests would fit better than lit-tests for this purpose.
Eg. showing that if the RangeSet includes the MIN, then the negated RangeSet also includes that.
And the negated RangeSet really unites consecutive ranges.

Please note that I'm not a math expert and I haven't spent much time working with RangeSets.

Thank you for fixing this issue!

Please add a bit more tests where we can see that the negated of unsigned range of [n..m] is UINT_MAX-m+1..UINT_MAX-n+1].

@steakhal, thank you for your time!
@baloghadamsoftware

Please add a bit more tests where we can see that the negated of unsigned range of [n..m] is UINT_MAX-m+1..UINT_MAX-n+1].

Yes. I am writing them. Thanks for the review.

ASDenysPetrov edited the summary of this revision. (Show Details)

Improved Negate function in terms of handling [MIN,A]U[B,MAX] => [MIN,-B]U[-A,MAX] (previously was [MIN,MIN]U[MIN+1,-B]U[-A,MAX]).
Added unit test for Negate function.

ASDenysPetrov added a comment.EditedApr 16 2020, 3:14 AM

@baloghadamsoftware
Please, review my changes. If you think they are OK, could you, please, commit the patch on my behalf as an author:
git commit --amend --author="Denys Petrov <dpetrov@accesssoftek.com>"

The unit test you added is very welcome. However, please still extend the current tests (which are for the signed) also for the unsigned as well. Since this is a core change in the analyzer, let us wait for @NoQ as well before accepting it.

I'm impressed.
Though, I had some nits, please don't take it to heart :)

And consider joining the to the pre-merge beta testing project to benefit from buildbots and much more - for free.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
217

Should we take it as const ref to prevent copying?

235

AFAIK in a RangeSet the ranges are sorted by the From point in ascending order.
We should not check it for each range, only for the first.

Also, note that small and flat loops are more readable.
Consider using pure lambdas to reduce the body of the loop and of course to bind algorithms to names.

572–573

Couldn't we simplify the disjunction to single T->isEnumerationType() or to something similar?

clang/test/Analysis/constraint_manager_negate_difference.c
114–118

What does this test case demonstrate? Could you elaborate on that?
Why do you evaluate the x - y != 0 here twice?

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
23

According to the LLVM coding style we should use UpperCamelCase for variable names for new code.

Note that the Analyzer Core was written in a different style, we should follow that there instead (at least IMO).

27–28

AFAIK since std::initializer_list is just two pointers we should take it by value.

51

Generally, new expressions are a code smell. We should use something like an std::make_unique to prevent memory leaks on exceptions.
Though, I'm not sure if there is a similar function for llvm::IntrusiveRefCntPtr<T>s.

66

To be honest, I'm not sure if type is more descriptive than T.

68

AFAIK full sentences are required for comments.
https://llvm.org/docs/CodingStandards.html#commenting

113–120

Should we keep this?

ASDenysPetrov marked 9 inline comments as done.Apr 17 2020, 2:23 AM

@baloghadamsoftware

However, please still extend the current tests

I've looked for some appropriate tests to extend, but haven't found. What would you advise to use instead of mine?
@steakhal
Thanks for the comments.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
217

getMinValue returns APSInt by value, so it wouldn't make sense.

572–573

I've looked for similar single function, but there is no appropriate one. I decided not to add a new one to make patch more focused.

clang/test/Analysis/constraint_manager_negate_difference.c
114–118

Why do you evaluate the x - y != 0 here twice?

This is the root line which assertion occured on.
I'll add some comments.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
23

Here is a discussion VariableNames I was guide. Seems like we can use camelBack for new code. Am I right? Also RangeSetTest.cpp already uses mixed naming as you can see.

27–28

I'm not sure about should, since initializer_list is a container and it'd be consistent if we handle it like any other compound object despite its implementation (IMO). But I can change it if you wish.

51

I'll make it more safe.

66

It is useful for debug purposes, for instance you can change it to using type = int; to verify something. It also untie from template argument list and make the code more flexible.

68

I'll correct it.

113–120

I'm not sure, but I'd better keep it, because it is useful for debugging.

Refined Negate function. Divided by steps for clarity.
Made some changes in comments due to guideline.

ASDenysPetrov marked an inline comment as done.Apr 22 2020, 3:27 AM
ASDenysPetrov added inline comments.
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
217

My fault. Yes, you are right. I've missed &. I used to append & to the type, since it is more readable and actually is a part of type, but I won't debate with clang style guide :).

ASDenysPetrov edited the summary of this revision. (Show Details)

@baloghadamsoftware
I have added regression tests as you asked. You can now check them. Thanks.
@NoQ,
I kindly ask you to look at the changes, seems that it has a full set to be load-ready. I really need your feedback here, since the changes is in the core.

NoQ added a comment.May 3 2020, 2:44 PM

The math looks correct, thank you for fixing the crash and adding support for more cases!

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
286–287

I don't remember iterator invalidation rules for these containers and it gives me anxiety. Given that these containers are immutable, i wouldn't be surprised if iterators are indeed never invalidated (just keep pointing to the old container) but it definitely deserves a comment.

572–573

isIntegralOrEnumerationType(), i guess.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
27–28

initializer_list is a container

No, it's a view :)

51

I'd rather create ASTContext through tooling, like in other unittests.

113–120

No-no, we don't do that here >.>

If you constructed an awesome debugging facility and you want to save it for future generations, i'd recommend turning it into an actual facility, not just comments. Like, maybe, an unused function that can be invoked for debugging, or something like that.

ASDenysPetrov marked 4 inline comments as done.EditedMay 4 2020, 2:04 AM

Thank you for the feedback. I'll update the patch soon.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
286–287

Thanks for the notice. I'm not sure about iterator invalidation, so I'll just replace *iter2 with *newRanges.begin().

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
27–28

No, it's a view :)

Yes, you are right. OK, I'll change it to value argument.

51

I'll look into other tests and try to change to ASTContext.

113–120

OK, I'll move it to function.

@NoQ updated the patch. Review, please.

@NoQ , ping. Look please.

NoQ accepted this revision.May 21 2020, 3:22 AM
NoQ added a subscriber: vsavchenko.

Looks fantastic, thanks! I guess let's race with @vsavchenko on whoever commits first :p

This revision is now accepted and ready to land.May 21 2020, 3:22 AM

@NoQ @ASDenysPetrov I will rebase my changes - no worries :)

@NoQ many thanks. I'll land it.

This revision was automatically updated to reflect the committed changes.