This is an archive of the discontinued LLVM Phabricator instance.

[analyzer] Add a new factory function RangeSet::Factory::invert
AcceptedPublic

Authored by ASDenysPetrov on Jul 22 2022, 10:17 AM.

Details

Summary

Add a new factory function RangeSet::Factory::invert. It performs an inversion operation on the given set and produces a new one as a result. The inversion of the set is a set containing all the values except those which are in the original one.

NOTE: User shall guarantee that the given set is not empty.

Example:
original: int8[0, 42] inverse: int8[-128, -1]U[43, 127];
original: int8[-128, 127] inverse: int8[];
original: [] inverse: raise an assertion.

The motivation is to extend the set of operations that can be performed on range sets. Specifically, this function is needed for the next patch in the stack.

Diff Detail

Event Timeline

ASDenysPetrov created this revision.Jul 22 2022, 10:17 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 22 2022, 10:17 AM
ASDenysPetrov requested review of this revision.Jul 22 2022, 10:17 AM

The motivation is to extend the set of operations that can be performed on range sets. Specifically, this function is needed for the next patch in the stack.

Would be great to see the motivation clearly and early. What will be the next patch about?

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

Could you please document this function and its complexity? (O(N) where N is the number of elements of the RangeSet.)

728–729

There might be a flaw here. Should this be == instead of != ?
Consider e.g. when What has two elements [[MIN, -1], [1, MAX]] then the inverse should be [0,0] which has size 1.

734–735

No goto please. There are better alternatives, e.g. you could have two different while loops for each cases.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
281

I think, it would make sense to test the composition of two invert operations to identity.

EXPECT_EQ(What, F.invert(F.invert(What));

This, of course requires that empty set is a possible input.

1101

Good tests!

1130

I'd expect that inversion on finite sets is an invert-able function thus

this->checkInvert({}, {MIN, MAX});

would make sense instead of assertion.

Besides, it would make sense to test the composition of two invert operations to identity.

ASDenysPetrov marked 6 inline comments as done.Jul 27 2022, 12:57 PM

@martong Thanks for review.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
728–729

Yes. Definetely. It remained from my previous version of calculation.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
281

Great idea. I will do it, except [].

1130

I'm afraid the function would be overheaded and less usable. Why do we have an assertion here? I thought about this. This is kinda a tradeoff.

What range would be a correct range from inversion of []? [-128, 127]? [0, 65535]?
In order to make [MIN, MAX] from empty range [] we should know the exact APSIntType. We extract the type from the given range What.getAPSIntType();.

But though, let's consider we have QualType as a second parameter. We have two options about what type to use.

  1. Always use the second parameter. The function would not only invert but do what castTo actually do. Such behavior would violates a single responsibility principle and duplicate the functionality.
  2. Always use the type from the given range and for the case of empty range from the second parameter. The function contract would be more complex and obscure.

So, I decided not to introduce a new parameter and shift responsibility to the user. Empty range is an edge case when we usually produce infeasible state or use infer(QualType). This may pretty fit with what user is going to do first before using invert, so it shouldn't affect the convinience of function usage too much.

ASDenysPetrov marked 3 inline comments as done.Jul 27 2022, 12:58 PM

Now I'm working on the next patch and you'll see a motivation soon.

Make changes according to the remarks.

  • Add complexity to function description.
  • Rewrite the loop making it deterministic.
  • Add back invert operation to the tests.

Now I'm working on the next patch and you'll see a motivation soon.

Thanks for the update! Looks good, but I am still waiting with my formal approve to understand the motivation.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
1130

Okay, I see your point.

So, considering RangeSet::Factory::invert(RangeSet What) we have only one parameter and that is the RangeSet to be inverted. And that set might be empty and in that case we are left without any type information, thus there is no way to return [MIN, MAX]. Please correct me if I am wrong.

@martong

Now I'm working on the next patch and you'll see a motivation soon.

Here is the motivation but it still causes some tests failure D131006.

ASDenysPetrov added inline comments.Aug 3 2022, 11:14 AM
clang/unittests/StaticAnalyzer/RangeSetTest.cpp
1130

Exactly. That's what I'm talking about..

martong accepted this revision.Aug 4 2022, 2:51 AM

LGTM! Nice work!

This revision is now accepted and ready to land.Aug 4 2022, 2:51 AM
ASDenysPetrov added a comment.EditedAug 5 2022, 11:51 AM

Thank you. I prefer to load this along with the motivation part D131006.

The motivation for this revision is lost due to the logical mistake in the later. However, this revision could be used for other improvements in the future. I will not merge it until new motivation has become.