[analyzer][solver] Redesign constraint ranges data structure

[vsavchenko]

Summary

ImmutableSet doesn't seem like the perfect fit for the RangeSet
data structure. It is good for saving memory in a persistent
setting, but not for the case when the population of the container
is tiny. This commit replaces RangeSet implementation and
redesigns the most common operations to be more efficient.

[grandinj]

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

88

Just curious - if they mostly contain 1 or 2 elements, why is N == 4 here?

[vsavchenko]

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

88

Essentially, the main factor is intuition 😆
The main idea here is that allocations are the single most expensive thing about ranges, so I want to avoid extra allocations not for 60% of range sets, but for 90%. I still should definitely measure performance difference for different values of N and gather some stats about the lengths.

[NoQ]

If the numbers are confirmed to be as good as what i've sneak-peeked so far, that should be pretty amazing. Also whoa, test coverage!~

WDYT about moving introducing a generic "SmallImmutableSet" in llvm/ADT to back your implementation?

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

88

Given that you pass those by pointers, i suspect you don't need to fix the size at all. In fact the small-size of the small vector is, by design, a runtime value and you can use llvm::SmallVectorImpl * instead, which can point to SmallVector of any small-size. This would allow you to allocate small vectors of variable length which you can take advantage of whenever you know the length in advance.

135

"But what about setGet()???" - some user, probably :)

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

119

Given that we're certain from the start that the container will be persistent, can we save a copy by directly asking the factory to allocate a fresh container?

Also this seems to be one of the cases where variable-sized small vectors would make sense.

281

Thanks a lot for adding those comments. These methods were confusing as heck.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

206

Why is it necessary to specify this-> here?

[vsavchenko]

In D86465#2235289, @NoQ wrote:

If the numbers are confirmed to be as good as what i've sneak-peeked so far, that should be pretty amazing. Also whoa, test coverage!~

I'll add the charts with performance in the next couple of days

WDYT about moving introducing a generic "SmallImmutableSet" in llvm/ADT to back your implementation?

Oof, it is not really possible. First of all, existing RangeSet didn't really ensure that ranges do not intersect (add is/was not checking for that), and this is left for the user. Additionally, it is designed and optimized specifically for RangeSet queries and operations. Like intersect and contains in a more generic Set sense mean entirely different things.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

88

Sounds reasonable, I'll give it a shot!

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

281

😊

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

206

It is due to shenanigans in test fixtures implementation. I didn't find a better workaround and other tests for other components also use this-> as far as I checked :-(

[vsavchenko]

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

119

Surprisingly this is not the case, it is cheaper to do whatever you want on small vectors on the stack and check if we already allocated it.
So, it is a deliberate choice to do it this way (you can see it in the comment inside of the makePersistent function.

[vsavchenko]

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

88

On the second thought, it's not going to be pretty. I still will need to allocate SmallVector<..., N>, where N is a compile-time constant, so it would be a big old switch where I "convert" run-time values into compile-time values so-to-speak.

Additionally, the involvement of SmallVector doesn't seem to be necessary at all because in this setting we don't use the main feature of it that it can grow larger than this size onto the heap. So, we can simply do the same trick with ArrayRef and std::array, but with less ambiguity.

However, one of the benefits of the current approach is "let's allocate as little as possible". It does the operation, checks if we allocated space for a container with these contents, and allocates it only if not. It is MUCH cheaper to do the operation and find out that we already have one like this or copy it to the newly allocated place than allocating it every time.

[steakhal]

This is a huge change, I've got pretty tired at the end of the review.
I haven't checked the test-cases too deeply.

I've found only minor typos, clarity enhancement opportunities etc. nothing serious.
It was awesome to see how this code can be improved, even becoming comprehensible.

Sorry for my nit spam if it needs further discussion - but it looks good to me.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

35–36

I don't think we should inherit from standard type. It should be a private member instead.
https://quuxplusone.github.io/blog/2018/12/11/dont-inherit-from-std-types/#never-ever-inherit-from-any-std

51

We have dump methods all over the place. Except this.
I propose to rename this to dump.

53–55

It's a good practice to define comparison operators as friend functions inline.
Even if we don't rely on implicit conversions.

110

I think it should be std::size_t.

118–123

What about merge or combine? I know that union is a keyword thus we can not use.

135

Why don't we call this createSetOf?
And createEmptySet.
I know that we don't create the empty set, but then what does a factory if not create stuff?

149–160

I think an example would be awesome here.

170–174

Why does this operation take O(N) time? Shouldn't be O(logN) instead?

190–193

195–196

203

As commented later, this function worth to be documented.

207–208

Why do we need to explicitly spell the RangeSet here?

210–211

213–215

222

class Factory is a nested class of RangeSet, so it can already access all private parts.

225–228

If this is the Rule of 5, where is the defaulted destructor?

252–259

Finally, we got this, awesome!

261

269

If we implement equality, we should also support inequality.

272–273

Missing explicit.

275–276

TBH, I don't even know what the pin function does.
Should we consider a more descriptive name instead?
Maybe some docs would come handy too.

277

If it's a read-only operation why don't we take by value? Just like contains does.
If it has side-effects which modify the Point, why is that not documented here?

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

146–149

Off-topic: Why do the Allocate and the similar allocator functions return T* if there is NO living object there (yet).
There will be, only if the placement constructor called...
I highly agree with you using void * there.

177–178

181–188

Previously we had an early empty check here.
Why don't we have that now?
Same question for the other overload.

281

I agree. These are black magic. xD

322–325

It could definitely bear a longer name.

367–370

375

It's unfortunate to refer to the next subrange by the ++Second.
Since operator++ has a side-effect I would recommend the Second+1 instead.

384

It's probably a personal taste though.
I think better to use the more verbose way incrementing an iterator if you are in the body of the loop.
It catches more attention.

412–417

What.size() seems not justified here.
As you described previously, there is a case when the resulting range will have one more range then the previous one had.
negate([MIN, X] => [MIN,MIN] U [-X,MAX]

431

498

Can we use range-based for loops?

[vsavchenko]

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

110

Yeah, I didn't see a unified stand of the community on this matter. It looks like both options are pretty widespread. I mimicked SmallVector.h, but I can easily change it.

118–123

Maybe, but the real union function is not present. And I think that in the original code it is add to hint that it's not really a union and nothing complex is done here. Maybe something like mergeUnchecked would work.

[vsavchenko]

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

149–160

Agree, I simply copy-pasted the comment, but it would be better to expand it a bit because it might be confusing.

170–174

We still create a copy of an old vector to maintain persistence, that's why it's O(N).

190–193

The same thing with this comment, I think I'll rework it even more

195–196

+1

203

I didn't think that it's necessary because of the fact that it's private, but it's pretty important, so I'll do it.

207–208

Good point!

210–211

+1

213–215

+1

225–228

It is, and it is forgotten, good catch!

269

Sure!

272–273

More like missing /* implicit */ because it is intentional

277

Good point. Essentially it modifies the argument the same way pin functions do - by changing its type. I'll add the comments

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

146–149

100% agree. It might be a source of mistakes where the type system doesn't help.

177–178

I don't really see the benefits of one way over another and as I said in another comment, I don't really like to pay for an extra copy with iterators as just a rule of thumb.

181–188

I'll add assertions checking for non-emptiness.
Essentially, it is a private function and the callers ensure this precondition.

322–325

I think that there is nothing wrong in spelling out std::swap twice.
And do we have a naming convention for lambdas, is it a variable or a function from a naming perspective?

367–370

OK

375

NP

384

It basically makes it Second++, and even though for these iterators it doesn't really matter I prefer not to pay extra copy when I don't need it.

498

We sure can, I wanted to change it but forgot

[vsavchenko]

Here are some benchmarking results.
In docker:

Natively on my Mac (no memory measurements due to this issue during psutil installation):

[martong]

In D86465#2238379, @vsavchenko wrote:

Here are some benchmarking results.
In docker:

Natively on my Mac (no memory measurements due to this issue during psutil installation):

These are really promising figures, nice work! (And the measurement stuff itself is also a great addition, thanks for that!)
Not that it would matter much, but I was just wondering why there is a slightly bigger memory usage in some of the docker/small projects? The most conspicuous is oatpp.

[steakhal]

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

118–123

Now I get it. Let's keep it as-is.
Might worth highlighting the **with all ranges from both** part though.

170–174

Thanks. BTW I just forgot about this comment :D

272–273

It doesn't have a too long identifier.
The users can always refer to it auto R = RangeSet(...), so we still don't repeat ourselves.
Do you have any particular counterexample?
Probably the tests will become slightly more bloated but eh. whatever.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

177–178

Iterators supposed to be cheap to copy. That is why we take them by value all over the place.
IMO it should boil down to the very same codegen in both cases. https://godbolt.org/z/8x1zMh

To prove it, I disassembled the following functions in release clang build:

// _Z21raw_rangeset_iteratorN5clang4ento8RangeSetE
const llvm::APSInt &raw_rangeset_iterator(RangeSet What) {
  RangeSet::iterator It = What.begin();
  --It;
  return It->To();
}
// _Z26std_prev_rangeset_iteratorN5clang4ento8RangeSetE
const llvm::APSInt &std_prev_rangeset_iterator(RangeSet What) {
  RangeSet::iterator It = What.begin();
  return std::prev(It)->To();
}

(gdb) disassemble _Z21raw_rangeset_iteratorN5clang4ento8RangeSetE
Dump of assembler code for function raw_rangeset_iterator(clang::ento::RangeSet):
   0x0000000006102b10 <+0>:	mov    (%rdi),%rax
   0x0000000006102b13 <+3>:	mov    -0x8(%rax),%rax
   0x0000000006102b17 <+7>:	retq   
End of assembler dump.

(gdb) disassemble _Z26std_prev_rangeset_iteratorN5clang4ento8RangeSetE
Dump of assembler code for function _Z26std_prev_rangeset_iteratorN5clang4ento8RangeSetE:
   0x00000000061040d0 <+0>:	mov    (%rdi),%rax
   0x00000000061040d3 <+3>:	mov    -0x8(%rax),%rax
   0x00000000061040d7 <+7>:	retq   
End of assembler dump.

322–325

That's a good question :)
I would say that its a variable, since you can mark it const, otherwise you could overwrite it. xD But that's a different story I think.
About the swap thingie, its a good practice to respect ADL for functions which know to be used via ADL.
Even if we don't depend on ADL in this particular case.

[vsavchenko]

Fix review remarks

[vsavchenko]

In D86465#2238614, @martong wrote:

These are really promising figures, nice work! (And the measurement stuff itself is also a great addition, thanks for that!)

Thanks 😊

Not that it would matter much, but I was just wondering why there is a slightly bigger memory usage in some of the docker/small projects? The most conspicuous is oatpp.

The measurements fluctuate quite significantly and as you can see the means for both old and new experiments for oatpp are pretty close. So, I would say that the memory differences are not conclusive.
This being said, the performance measurements should also be taken with a grain of salt. We can't really say that we get 5-10% performance improvement for sure, but that analysis tends to be faster instead.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

53–55

It doesn't seem like there is a single opinion on this in the codebase.

135

The naming is this way to be consistent with ImmutableSet::Factory

272–273

These constructors are private and used in Factory methods. IMO they make those methods less cluttered.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

322–325

I'm sorry but I still don't get the importance of dropping std:: here.

[steakhal]

Previously, I liked this. Now I love it!
The benchmarks look promising as well.

I think I can not convince you about not modifying iterators using ++,--, etc. outside of loop-expressions. So be it :D

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

51

How about marking this LLVM_DUMP_METHOD?
Also, defining the operator<< would come handly later.

53–55

Okay.

106

Shouldn't we call this const_iterator?

135

Makes sense.

205

207

268

Btw in C++20 we will have a way expressing this: explicit(false)

271–280

Aww, excellent. Thanks.

272–273

Okay.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

322–325

Since we don't rely on Argument Dependent Lookup in this particular case, both versions do the same.
So it's perfectly fine as-is.
You should interpret my previous comment in a broader sense, like a guideline.
Which is meaningful mostly in generic programming.

414

462–470

It might be overkill, but we can do this using transform.

495–507

Hmm, we could simplify this further, assuming Range::operator<< is defined.

[ASDenysPetrov]

Here is my five cents. I haven't done with the review yet. I'm gonna return to it a bit later.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

58

I'm not sure about optimizations but it seems like it could have less commands by omiting this.

135

IMO function's name should match to what it does. If it creates smth, so its name should starts with create. Even if all other functions have misleading names it doesn't mean we are delegated to ignore this fact.
My another suggestion is that Set is a common term to RangeSet. So I'd prefer to use getRangeSet instead.

[ASDenysPetrov]

I didn't check correctness of each Factory function but if it passes all tests and improves performance, I think it's enough.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

73–74

That's very usefull description for reviewers, but I think is redundant for newcomers, when you're reading this you can't understand why it compares to ImmutableSet at all. I think this preamble only relates to the Summary of this patch as the core reason of this change.
You can just mention the fact that formerly it was an ImmutableSet. See http for details.

129

We can add one more instance of add (and maybe others): RangeSet add(RangeSet original, llvm::APSInt &point);.
Since we have RangeSet(Factory &F, const llvm::APSInt &Point) ctor, why wouldn't we have similar functionality in the Factory?

It could simplify function RangeSetTest::from in tests and be useful across the code on the whole.

174

IMHO you should change params with each other:
deletePoint(const llvm::APSInt &Point, RangeSet From) -> deletePoint(RangeSet Original, const llvm::APSInt &Point)
This will look more consistent with other interfaces like in add or intersect functions.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

105

Explain, please, what's the matter to use wrap everywhere, not just call checkNegateImpl explicitly?
Won't the call works and looks the same? Like:

this->checkNegateImpl({{MIN, A}}, {{MIN, MIN}, {D, MAX}});

185

Thank you for making it in a proper way, instead of a list with different type instantiations.

[ASDenysPetrov]

My propositions for the function negate.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

433–434

Here you can just move What. And after that you can do Result.reserve.

509

Here you can reuse SampleValue and simplify a bit this snippet.

[ASDenysPetrov]

@vsavchenko
Hi, I actually want this patch goes developing and be loaded. It's really the worth one. Is it abandoned?

[vsavchenko]

In D86465#2569403, @ASDenysPetrov wrote:

@vsavchenko
Hi, I actually want this patch goes developing and be loaded. It's really the worth one. Is it abandoned?

Hi, nope. Just got postponed, I'll address the review comments soon!

[vsavchenko]

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

433–434

What is a persistent range set, so moving it or making it persistent won't do, but we indeed can simply return What.

[vsavchenko]

Rebase and address review comments

[vsavchenko]

Oof, it took me quite some time to come back to this.
I don't think that I'll be able to gather more performance-related data than I already did, so if it's OK with y'all, we can land it.
@NoQ @steakhal @ASDenysPetrov ?

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

73–74

I don't want to fully remove this comment because this is a comment explaining implementation detail, which I believe newcomers can skip altogether.
However, I will change it to say that it was formerly an immutable set.

205

That's a bit too verbose for the header IMO.

207

The same as above. I don't want to mention caches or arenas for the sake of hiding those as implementation detail. One might rightfully argue that having these methods here also leaks implementation detail into the header file, but without a pImpl, which I believe is not very widespread in the LLVM codebase, it's not possible to hide these.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

462–470

Yeah, I'd say that it is wordier.

495–507

I think it looks a bit clearer with llvm::interleaveComma

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

105

Sure, we want to use a "raw" version of ranges and range sets everywhere in the tests for the simplicity of the test. Here I got bored writing from(Arg0), from(Arg1), ... and went with this.

185

Oh yes, it would've been a true nightmare repeating every test for every type

[vsavchenko]

Add minor fix in tests

[steakhal]

Ah, I wanted to give it a go, but the bots caught an assertion failure for the parent revision of this. See the details at the Bugzilla ticket.

What is more concerning is that this patch resolves that assertion failure. I guess it implies it can not be NFC?
Regardless, I'm gonna wait to get that issue fixed before I have a deeper look.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

186

You should probably test _ExtInts as well.

[steakhal]

Given that it did not change any reports in our testbench it seems to be safe to land it.

It clearly improves the API significantly, so I'm not opposing.
Really good work @vsavchenko.

PS: If should support _ExtInts as well, even if they are not too common.
Please try to fill this gap, before you push your changes.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

495–507

Awesome!

[vsavchenko]

In D86465#2637186, @steakhal wrote:

Ah, I wanted to give it a go, but the bots caught an assertion failure for the parent revision of this. See the details at the Bugzilla ticket.

What is more concerning is that this patch resolves that assertion failure. I guess it implies it can not be NFC?
Regardless, I'm gonna wait to get that issue fixed before I have a deeper look.

Hmm, I tried it on that test without the fix, and the assertion failure is there.

[vsavchenko]

In D86465#2640687, @steakhal wrote:

Given that it did not change any reports in our testbench it seems to be safe to land it.

It clearly improves the API significantly, so I'm not opposing.
Really good work @vsavchenko.

Thanks 😊

PS: If should support _ExtInts as well, even if they are not too common.
Please try to fill this gap, before you push your changes.

I do have a bit of a struggle here. This is a unit-test and thus should be compiled for all of the supported architectures by all of the supported compilers.
Is there a __has_feature or something for me to check if _ExtInt can be used?

[steakhal]

In D86465#2640765, @vsavchenko wrote:

I do have a bit of a struggle here. This is a unit-test and thus should be compiled for all of the supported architectures by all of the supported compilers.
Is there a __has_feature or something for me to check if _ExtInt can be used?

Aa, I get it. It is actually a clang specific extension. By checking git blame, it seems to be a quite new feature, clang-11+.
What about something like this?

using IntTypes = ::Types<int8_t, uint8_t, int16_t, uint16_t, int32_t,
                         uint32_t, int64_t, uint64_t
#if defined(__clang__) && __clang_major__ >= 11
                         , __int128_t, __uint128_t
                         , signed _ExtInt(200)
                         , unsigned _ExtInt(200)
#endif
>;

https://godbolt.org/z/GfMfWEz88 Seems to work for a number of compilers.

[vsavchenko]

In D86465#2640842, @steakhal wrote:

In D86465#2640765, @vsavchenko wrote:

I do have a bit of a struggle here. This is a unit-test and thus should be compiled for all of the supported architectures by all of the supported compilers.
Is there a __has_feature or something for me to check if _ExtInt can be used?

Aa, I get it. It is actually a clang specific extension. By checking git blame, it seems to be a quite new feature, clang-11+.
What about something like this?

using IntTypes = ::Types<int8_t, uint8_t, int16_t, uint16_t, int32_t,
                         uint32_t, int64_t, uint64_t
#if defined(__clang__) && __clang_major__ >= 11
                         , __int128_t, __uint128_t
                         , signed _ExtInt(200)
                         , unsigned _ExtInt(200)
#endif
>;

https://godbolt.org/z/GfMfWEz88 Seems to work for a number of compilers.

This is not only a compiler feature, it also should be supported by the target architecture:
https://godbolt.org/z/ddjYYx9x6

[steakhal]

In D86465#2640875, @vsavchenko wrote:

This is not only a compiler feature, it also should be supported by the target architecture:
https://godbolt.org/z/ddjYYx9x6

It's getting complicated then xD. I guess we should complement unittests with LIT tests?
You can know there that clang is recent enough and pinning the target triple would also solve this.

[vsavchenko]

In D86465#2640954, @steakhal wrote:

In D86465#2640875, @vsavchenko wrote:

This is not only a compiler feature, it also should be supported by the target architecture:
https://godbolt.org/z/ddjYYx9x6

It's getting complicated then xD. I guess we should complement unittests with LIT tests?
You can know there that clang is recent enough and pinning the target triple would also solve this.

My suggestion would be to check these separately with a possible fix.

[steakhal]

In D86465#2640958, @vsavchenko wrote:

In D86465#2640954, @steakhal wrote:

It's getting complicated then xD. I guess we should complement unittests with LIT tests?
You can know there that clang is recent enough and pinning the target triple would also solve this.

My suggestion would be to check these separately with a possible fix.

Feel free to push this as-is. But try to cover these cases later if you can.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H
 #define LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H
 
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h"
+#include "llvm/Support/Allocator.h"
 
 namespace clang {
 
 namespace ento {
 
 /// A Range represents the closed range [from, to].  The caller must
 /// guarantee that from <= to.  Note that Range is immutable, so as not
 /// to subvert RangeSet's immutability.
 class Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> {
 public:
-  Range(const llvm::APSInt &from, const llvm::APSInt &to)
-      : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) {
-    assert(from <= to);
+  Range(const llvm::APSInt &From, const llvm::APSInt &To)
+      : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&From, &To) {
+    assert(From <= To);
   }
 
-  Range(const llvm::APSInt &point)
-      : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&point, &point) {}
+  Range(const llvm::APSInt &Point)
+      : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&Point, &Point) {}
 
-  bool Includes(const llvm::APSInt &v) const {
-    return *first <= v && v <= *second;
+  bool Includes(const llvm::APSInt &Point) const {
+    return From() <= Point && Point <= To();
   }
   const llvm::APSInt &From() const { return *first; }
   const llvm::APSInt &To() const { return *second; }
   const llvm::APSInt *getConcreteValue() const {
     return &From() == &To() ? &From() : nullptr;
   }
 
   void Profile(llvm::FoldingSetNodeID &ID) const {
     ID.AddPointer(&From());
     ID.AddPointer(&To());
   }
+  void print(raw_ostream &OS) const;
+
+  // In order to keep non-overlapping ranges sorted, we can compare only From
+  // points.
+  inline bool operator<(const Range &RHS) const { return From() < RHS.From(); }
 };
 
-class RangeTrait : public llvm::ImutContainerInfo<Range> {
+/// @class RangeSet is a persistent set of non-overlapping ranges.
+///
+/// New RangeSet objects can be ONLY produced by RangeSet::Factory object, which
+/// also supports the most common operations performed on range sets.
+///
+/// Empty set corresponds to an overly constrained symbol meaning that there
+/// are no possible values for that symbol.
+class RangeSet {
 public:
-  // When comparing if one Range is less than another, we should compare
-  // the actual APSInt values instead of their pointers.  This keeps the order
-  // consistent (instead of comparing by pointer values) and can potentially
-  // be used to speed up some of the operations in RangeSet.
-  static inline bool isLess(key_type_ref lhs, key_type_ref rhs) {
-    return *lhs.first < *rhs.first ||
-           (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second);
+  class Factory;
+
+private:
+  // We use llvm::SmallVector as the underlying container for the following
+  // reasons:
+  //
+  //   * Range sets are usually very simple, 1 or 2 ranges.
+  //     That's why llvm::ImmutableSet is not perfect.
+  //
+  //   * Ranges in sets are NOT overlapping, so it is natural to keep them
+  //     sorted for efficient operations and queries.  For this reason,
+  //     llvm::SmallSet doesn't fit the requirements, it is not sorted when it
+  //     is a vector.
+  //
+  //   * Range set operations usually a bit harder than add/remove a range.
+  //     Complex operations might do many of those for just one range set.
+  //     This makes llvm::ImmutableSet inefficient for our purposes as we want
+  //     to make these operations BOTH immutable AND efficient.
+  //
+  //   * Iteration over ranges is widespread and a more cache-friendly
+  //     structure is preferred.
+  using ImplType = llvm::SmallVector<Range, 4>;
+
+  struct ContainerType : public ImplType, public llvm::FoldingSetNode {
+    void Profile(llvm::FoldingSetNodeID &ID) const {
+      for (const Range &It : *this) {
+        It.Profile(ID);
+      }
     }
   };
+  // This is a non-owning pointer to an actual container.
+  // The memory is fully managed by the factory and is alive as long as the
+  // factory itself is alive.
+  // It is a pointer as opposed to a reference, so we can easily reassign
+  // RangeSet objects.
+  using UnderlyingType = const ContainerType *;
+  UnderlyingType Impl;
 
-/// RangeSet contains a set of ranges. If the set is empty, then
-///  there the value of a symbol is overly constrained and there are no
-///  possible values for that symbol.
-class RangeSet {
-  typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet;
-  PrimRangeSet ranges; // no need to make const, since it is an
-                       // ImmutableSet - this allows default operator=
-                       // to work.
 public:
-  typedef PrimRangeSet::Factory Factory;
-  typedef PrimRangeSet::iterator iterator;
+  using iterator = ImplType::const_iterator;
 
-  RangeSet(PrimRangeSet RS) : ranges(RS) {}
+  iterator begin() const { return Impl->begin(); }
+  iterator end() const { return Impl->end(); }
+  size_t size() const { return Impl->size(); }
 
-  /// Create a new set with all ranges of this set and RS.
+  bool isEmpty() const { return Impl->empty(); }
+
+  class Factory {
+  public:
+    Factory(BasicValueFactory &BV) : ValueFactory(BV) {}
+
+    /// Create a new set with all ranges from both LHS and RHS.
+    /// Possible intersections are not checked here.
+    ///
+    /// Complexity: O(N + M)
+    ///             where N = size(LHS), M = size(RHS)
+    RangeSet add(RangeSet LHS, RangeSet RHS);
+    /// Create a new set with all ranges from the original set plus the new one.
     /// Possible intersections are not checked here.
-  RangeSet addRange(Factory &F, const RangeSet &RS) {
-    PrimRangeSet Ranges(RS.ranges);
-    for (const auto &range : ranges)
-      Ranges = F.add(Ranges, range);
-    return RangeSet(Ranges);
+    ///
+    /// Complexity: O(N)
+    ///             where N = size(Original)
+    RangeSet add(RangeSet Original, Range Element);
+
+    RangeSet getEmptySet() { return &EmptySet; }
+
+    /// Create a new set with just one range.
+    /// @{
+    RangeSet getSet(Range Origin);
+    RangeSet getSet(const llvm::APSInt &From, const llvm::APSInt &To) {
+      return getSet(Range(From, To));
     }
+    RangeSet getSet(const llvm::APSInt &Origin) {
+      return getSet(Origin, Origin);
+    }
+    /// @}
+
+    /// Intersect the given range sets.
+    ///
+    /// Complexity: O(N + M)
+    ///             where N = size(LHS), M = size(RHS)
+    RangeSet intersect(RangeSet LHS, RangeSet RHS);
+    /// Intersect the given set with the closed range [Lower, Upper].
+    ///
+    /// Unlike the Range type, this range uses modular arithmetic, corresponding
+    /// to the common treatment of C integer overflow. Thus, if the Lower bound
+    /// is greater than the Upper bound, the range is taken to wrap around. This
+    /// is equivalent to taking the intersection with the two ranges [Min,
+    /// Upper] and [Lower, Max], or, alternatively, /removing/ all integers
+    /// between Upper and Lower.
+    ///
+    /// Complexity: O(N)
+    ///             where N = size(What)
+    RangeSet intersect(RangeSet What, llvm::APSInt Lower, llvm::APSInt Upper);
+    /// Intersect the given range with the given point.
+    ///
+    /// The result can be either an empty set or a set containing the given
+    /// point depending on whether the point is in the range set.
+    ///
+    /// Complexity: O(logN)
+    ///             where N = size(What)
+    RangeSet intersect(RangeSet What, llvm::APSInt Point);
+
+    /// Delete the given point from the range set.
+    ///
+    /// Complexity: O(N)
+    ///             where N = size(From)
+    RangeSet deletePoint(const llvm::APSInt &Point, RangeSet From);
+    /// Negate the given range set.
+    ///
+    /// Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus
+    /// operation under the values of the type.
+    ///
+    /// We also handle MIN because applying unary minus to MIN does not change
+    /// it.
+    /// Example 1:
+    /// char x = -128;        // -128 is a MIN value in a range of 'char'
+    /// char y = -x;          // y: -128
+    ///
+    /// Example 2:
+    /// unsigned char x = 0;  // 0 is a MIN value in a range of 'unsigned char'
+    /// unsigned char y = -x; // y: 0
+    ///
+    /// And it makes us to separate the range
+    /// like [MIN, N] to [MIN, MIN] U [-N, MAX].
+    /// For instance, whole range is {-128..127} and subrange is [-128,-126],
+    /// thus [-128,-127,-126,...] negates to [-128,...,126,127].
+    ///
+    /// Negate restores disrupted ranges on bounds,
+    /// e.g. [MIN, B] => [MIN, MIN] U [-B, MAX] => [MIN, B].
+    ///
+    /// Complexity: O(N)
+    ///             where N = size(What)
+    RangeSet negate(RangeSet What);
 
-  iterator begin() const { return ranges.begin(); }
-  iterator end() const { return ranges.end(); }
+  private:
+    RangeSet makePersistent(ContainerType &&From);
+    ContainerType *construct(ContainerType &&From);
+    void destroy(const ContainerType *);
+
+    RangeSet intersect(const RangeSet::ContainerType &LHS,
+                       const RangeSet::ContainerType &RHS);
+
+    // Many operations inlcude producing new APSInt values and that's why
+    // we need this factory.
+    BasicValueFactory &ValueFactory;
+    // Allocator for all the created containers.
+    // Containers might own their own memory and that's why it is specific
+    // for the type, so it calls containter destructors upon deletion.
+    llvm::SpecificBumpPtrAllocator<ContainerType> Arena;
+    // Usually we deal with the same ranges and range sets over and over.
+    // Here we track all created containers and try not to repeat ourselves.
+    llvm::FoldingSet<ContainerType> Cache;
+    static ContainerType EmptySet;
 
-  bool isEmpty() const { return ranges.isEmpty(); }
+    friend class RangeSet;
+  };
 
-  /// Construct a new RangeSet representing '{ [from, to] }'.
-  RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to)
-      : ranges(F.add(F.getEmptySet(), Range(from, to))) {}
+  RangeSet(const RangeSet &) = default;
+  RangeSet &operator=(const RangeSet &) = default;
+  RangeSet(RangeSet &&) = default;
+  RangeSet &operator=(RangeSet &&) = default;
+
+  /// Construct a new RangeSet representing '{ [From, To] }'.
+  RangeSet(Factory &F, const llvm::APSInt &From, const llvm::APSInt &To)
+      : RangeSet(F.getSet(From, To)) {}
 
   /// Construct a new RangeSet representing the given point as a range.
-  RangeSet(Factory &F, const llvm::APSInt &point) : RangeSet(F, point, point) {}
+  RangeSet(Factory &F, const llvm::APSInt &Point) : RangeSet(F.getSet(Point)) {}
+
+  static void Profile(llvm::FoldingSetNodeID &ID, const RangeSet &RS) {
+    ID.AddPointer(RS.Impl);
+  }
 
   /// Profile - Generates a hash profile of this RangeSet for use
   ///  by FoldingSet.
-  void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); }
+  void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, *this); }
 
   /// getConcreteValue - If a symbol is contrained to equal a specific integer
   ///  constant then this method returns that value.  Otherwise, it returns
   ///  NULL.
   const llvm::APSInt *getConcreteValue() const {
-    return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr;
+    return Impl->size() == 1 ? begin()->getConcreteValue() : nullptr;
   }
 
   /// Get a minimal value covered by the ranges in the set
+  ///
+  /// Complexity: O(1)
   const llvm::APSInt &getMinValue() const;
   /// Get a maximal value covered by the ranges in the set
+  ///
+  /// Complexity: O(1)
   const llvm::APSInt &getMaxValue() const;
 
-private:
-  void IntersectInRange(BasicValueFactory &BV, Factory &F,
-                        const llvm::APSInt &Lower, const llvm::APSInt &Upper,
-                        PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
-                        PrimRangeSet::iterator &e) const;
+  /// Test whether the given point is contained in any of the ranges.
+  ///
+  /// Complexity: O(logN)
+  ///             where N = size(this)
+  bool contains(llvm::APSInt Point) const { return containsImpl(Point); }
 
-  bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
+  void print(raw_ostream &os) const;
 
-public:
-  RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower,
-                     llvm::APSInt Upper) const;
-  RangeSet Intersect(BasicValueFactory &BV, Factory &F,
-                     const RangeSet &Other) const;
-  RangeSet Negate(BasicValueFactory &BV, Factory &F) const;
-  RangeSet Delete(BasicValueFactory &BV, Factory &F,
-                  const llvm::APSInt &Point) const;
+  bool operator==(const RangeSet &Other) const { return *Impl == *Other.Impl; }
 
-  void print(raw_ostream &os) const;
+private:
+  RangeSet(ContainerType *RawContainer) : Impl(RawContainer) {}
+  RangeSet(UnderlyingType Ptr) : Impl(Ptr) {}
 
-  bool operator==(const RangeSet &other) const {
-    return ranges == other.ranges;
-  }
+  bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
+  bool pin(llvm::APSInt &Point) const;
+  bool containsImpl(llvm::APSInt &Point) const;
+
+  friend class Factory;
 };
 
 using ConstraintMap = llvm::ImmutableMap<SymbolRef, RangeSet>;
 ConstraintMap getConstraintMap(ProgramStateRef State);
 
 class RangedConstraintManager : public SimpleConstraintManager {
 public:
   RangedConstraintManager(ExprEngine *EE, SValBuilder &SB)
       : SimpleConstraintManager(EE, SB) {}

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

 #include "clang/Basic/JsonSupport.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/ImmutableSet.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <iterator>
 
 using namespace clang;
 using namespace ento;
 
 // This class can be extended with other tables which will help to reason
 // about ranges more precisely.
 class OperatorRelationsTable {
   static_assert(BO_LT < BO_GT && BO_GT < BO_LE && BO_LE < BO_GE &&
TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP,
                              BinaryOperatorKind QueriedOP) const {
     return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];
   }
 
   TriStateKind getCmpOpStateForUnknownX2(BinaryOperatorKind CurrentOP) const {
     return CmpOpTable[getIndexFromOp(CurrentOP)][CmpOpCount];
   }
 };
+
 //===----------------------------------------------------------------------===//
 //                           RangeSet implementation
 //===----------------------------------------------------------------------===//
 
-void RangeSet::IntersectInRange(BasicValueFactory &BV, Factory &F,
-                                const llvm::APSInt &Lower,
-                                const llvm::APSInt &Upper,
-                                PrimRangeSet &newRanges,
-                                PrimRangeSet::iterator &i,
-                                PrimRangeSet::iterator &e) const {
-  // There are six cases for each range R in the set:
-  //   1. R is entirely before the intersection range.
-  //   2. R is entirely after the intersection range.
-  //   3. R contains the entire intersection range.
-  //   4. R starts before the intersection range and ends in the middle.
-  //   5. R starts in the middle of the intersection range and ends after it.
-  //   6. R is entirely contained in the intersection range.
-  // These correspond to each of the conditions below.
-  for (/* i = begin(), e = end() */; i != e; ++i) {
-    if (i->To() < Lower) {
-      continue;
-    }
-    if (i->From() > Upper) {
-      break;
-    }
+RangeSet::ContainerType RangeSet::Factory::EmptySet{};
+
+RangeSet RangeSet::Factory::add(RangeSet Original, Range Element) {
+  ContainerType Result;
+  Result.reserve(Original.size() + 1);
+
+  iterator Lower = llvm::lower_bound(Original, Element);
+  Result.insert(Result.end(), Original.begin(), Lower);
+  Result.push_back(Element);
+  Result.insert(Result.end(), Lower, Original.end());
+
+  return makePersistent(std::move(Result));
+
+RangeSet RangeSet::Factory::getSet(Range From) {
+  ContainerType Result;
+  Result.push_back(From);
+  return makePersistent(std::move(Result));
 
-    if (i->Includes(Lower)) {
-      if (i->Includes(Upper)) {
-        newRanges =
-            F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper)));
-        break;
-      } else
-        newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To()));
-    } else {
-      if (i->Includes(Upper)) {
-        newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper)));
-        break;
-      } else
-        newRanges = F.add(newRanges, *i);
-    }
-  }
+RangeSet RangeSet::Factory::makePersistent(ContainerType &&From) {
+  llvm::FoldingSetNodeID ID;
+  void *InsertPos;
+
+  From.Profile(ID);
+  ContainerType *Result = Cache.FindNodeOrInsertPos(ID, InsertPos);
+
+  if (!Result) {
+    // It is cheaper to fully construct the resulting range on stack
+    // and move it to the freshly allocated buffer if we don't have
+    // a set like this already.
+    Result = construct(std::move(From));
+    Cache.InsertNode(Result, InsertPos);
+  }
+
+  return Result;
+
+RangeSet::ContainerType *RangeSet::Factory::construct(ContainerType &&From) {
+  void *Buffer = Arena.Allocate();
+  return new (Buffer) ContainerType(std::move(From));
+
+RangeSet RangeSet::Factory::add(RangeSet LHS, RangeSet RHS) {
+  ContainerType Result;
+  std::merge(LHS.begin(), LHS.end(), RHS.begin(), RHS.end(),
+             std::back_inserter(Result));
+  return makePersistent(std::move(Result));
 }
 
 const llvm::APSInt &RangeSet::getMinValue() const {
   assert(!isEmpty());
   return begin()->From();
 }
 
 const llvm::APSInt &RangeSet::getMaxValue() const {
   assert(!isEmpty());
-  // NOTE: It's a shame that we can't implement 'getMaxValue' without scanning
-  //       the whole tree to get to the last element.
-  //       llvm::ImmutableSet should support decrement for 'end' iterators
-  //       or reverse order iteration.
-  auto It = begin();
-  for (auto End = end(); std::next(It) != End; ++It) {
-  }
-  return It->To();
+  return std::prev(end())->To();
+
+bool RangeSet::containsImpl(llvm::APSInt &Point) const {
+  if (isEmpty() || !pin(Point))
+    return false;
+
+  Range Dummy(Point);
+  iterator It = llvm::upper_bound(*this, Dummy);
+  if (It == begin())
+    return false;
+
+  --It;
+  return It->Includes(Point);
 }
 
-bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
-  if (isEmpty()) {
-    // This range is already infeasible.
+bool RangeSet::pin(llvm::APSInt &Point) const {
+  APSIntType Type(getMinValue());
+  if (Type.testInRange(Point, true) != APSIntType::RTR_Within)
     return false;
-  }
+
+  Type.apply(Point);
+  return true;
 
+bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
   // This function has nine cases, the cartesian product of range-testing
   // both the upper and lower bounds against the symbol's type.
   // Each case requires a different pinning operation.
   // The function returns false if the described range is entirely outside
   // the range of values for the associated symbol.
   APSIntType Type(getMinValue());
   APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true);
   APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true);
case APSIntType::RTR_Above:
       break;
     }
     break;
   }
 
   return true;
 }
 
-// Returns a set containing the values in the receiving set, intersected with
-// the closed range [Lower, Upper]. Unlike the Range type, this range uses
-// modular arithmetic, corresponding to the common treatment of C integer
-// overflow. Thus, if the Lower bound is greater than the Upper bound, the
-// range is taken to wrap around. This is equivalent to taking the
-// intersection with the two ranges [Min, Upper] and [Lower, Max],
-// or, alternatively, /removing/ all integers between Upper and Lower.
-RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
-                             llvm::APSInt Lower, llvm::APSInt Upper) const {
-  PrimRangeSet newRanges = F.getEmptySet();
+RangeSet RangeSet::Factory::intersect(RangeSet What, llvm::APSInt Lower,
+                                      llvm::APSInt Upper) {
+  if (What.isEmpty() || !What.pin(Lower, Upper))
+    return getEmptySet();
+
+  ContainerType DummyContainer;
+
+  if (Lower <= Upper) {
+    // [Lower, Upper] is a regular range.
+    //
+    // Shortcut: check that there is even a possibility of the intersection
+    //           by checking the two following situations:
+    //
+    //               <---[  What  ]---[------]------>
+    //                              Lower  Upper
+    //                            -or-
+    //               <----[------]----[  What  ]---->
+    //                  Lower  Upper
+    if (What.getMaxValue() < Lower || Upper < What.getMinValue())
+      return getEmptySet();
 
-  if (isEmpty() || !pin(Lower, Upper))
-    return newRanges;
+    DummyContainer.push_back(
+        Range(ValueFactory.getValue(Lower), ValueFactory.getValue(Upper)));
+  } else {
+    // [Lower, Upper] is an inverted range, i.e. [MIN, Upper] U [Lower, MAX]
+    //
+    // Shortcut: check that there is even a possibility of the intersection
+    //           by checking the following situation:
+    //
+    //               <------]---[  What  ]---[------>
+    //                    Upper             Lower
+    if (What.getMaxValue() < Lower && Upper < What.getMinValue())
+      return getEmptySet();
 
-  PrimRangeSet::iterator i = begin(), e = end();
-  if (Lower <= Upper)
-    IntersectInRange(BV, F, Lower, Upper, newRanges, i, e);
-  else {
-    // The order of the next two statements is important!
-    // IntersectInRange() does not reset the iteration state for i and e.
-    // Therefore, the lower range most be handled first.
-    IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e);
-    IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e);
+    DummyContainer.push_back(
+        Range(ValueFactory.getMinValue(Upper), ValueFactory.getValue(Upper)));
+    DummyContainer.push_back(
+        Range(ValueFactory.getValue(Lower), ValueFactory.getMaxValue(Lower)));
   }
 
-  return newRanges;
+  return intersect(*What.Impl, DummyContainer);
 }
 
-// Returns a set containing the values in the receiving set, intersected with
-// the range set passed as parameter.
-RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
-                             const RangeSet &Other) const {
-  PrimRangeSet newRanges = F.getEmptySet();
+RangeSet RangeSet::Factory::intersect(const RangeSet::ContainerType &LHS,
+                                      const RangeSet::ContainerType &RHS) {
+  ContainerType Result;
+  Result.reserve(std::max(LHS.size(), RHS.size()));
 
-  for (iterator i = Other.begin(), e = Other.end(); i != e; ++i) {
-    RangeSet newPiece = Intersect(BV, F, i->From(), i->To());
-    for (iterator j = newPiece.begin(), ee = newPiece.end(); j != ee; ++j) {
-      newRanges = F.add(newRanges, *j);
-    }
-  }
+  iterator First = LHS.begin(), Second = RHS.begin(), FirstEnd = LHS.end(),
+           SecondEnd = RHS.end();
 
-  return newRanges;
+  auto swap = [&First, &FirstEnd, &Second, &SecondEnd]() {
+    std::swap(First, Second);
+    std::swap(FirstEnd, SecondEnd);
+  };
+
+  // If we ran out of ranges in one set, but not the other,
+  // it means that those elements are definitely not in the
+  // intersection.
+  while (First != FirstEnd && Second != SecondEnd) {
+    // We want to keep the following invariant at all times:
+    //
+    //    ----[ First ---------------------->
+    //    --------[ Second ----------------->
+    if (Second->From() < First->From())
+      swap();
+
+    // Loop where the invariant holds:
+    do {
+      // Check for the following situation:
+      //
+      //    ----[ First ]--------------------->
+      //    ---------------[ Second ]--------->
+      //
+      // which means that...
+      if (Second->From() > First->To()) {
+        // ...First is not in the intersection.
+        //
+        // We should move on to the next range after First and break out of the
+        // loop because the invariant might not be true.
+        ++First;
+        break;
       }
 
-// Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus
-// operation under the values of the type.
+      // We have a guaranteed intersection at this point!
+      // And this is the current situation:
       //
-// We also handle MIN because applying unary minus to MIN does not change it.
-// Example 1:
-// char x = -128;        // -128 is a MIN value in a range of 'char'
-// char y = -x;          // y: -128
-// Example 2:
-// unsigned char x = 0;  // 0 is a MIN value in a range of 'unsigned char'
-// unsigned char y = -x; // y: 0
+      //    ----[   First   ]----------------->
+      //    -------[ Second ------------------>
       //
-// And it makes us to separate the range
-// like [MIN, N] to [MIN, MIN] U [-N,MAX].
-// For instance, whole range is {-128..127} and subrange is [-128,-126],
-// thus [-128,-127,-126,.....] negates to [-128,.....,126,127].
+      // Additionally, it definitely starts with Second->From().
+      const llvm::APSInt &IntersectionStart = Second->From();
+
+      // It is important to know which of the two ranges' ends
+      // is greater.  That "longer" range might have some other
+      // intersections, while the "shorter" range might not.
+      if (Second->To() > First->To())
+        // Here we make a decision to keep First as the "longer"
+        // range.
+        swap();
+
+      // At this point, we have the following situation:
       //
-// Negate restores disrupted ranges on bounds,
-// e.g. [MIN, B] => [MIN, MIN] U [-B, MAX] => [MIN, B].
-RangeSet RangeSet::Negate(BasicValueFactory &BV, Factory &F) const {
-  PrimRangeSet newRanges = F.getEmptySet();
+      //    ---- First      ]-------------------->
+      //    ---- Second ]--[  ++Second ---------->
+      //
+      // We don't know the relationship between First->From and
+      // Second->From and we don't know whether ++Second intersects
+      // with First.
+      //
+      // However, we know that [IntersectionStart, Second->To] is
+      // a part of the intersection...
+      Result.push_back(Range(IntersectionStart, Second->To()));
+      ++Second;
+      // ...and that the invariant will hold for a valid ++Second
+      // because First->From <= Second->To < ++Second->From.
+    } while (Second != SecondEnd);
+  }
+
+  if (Result.empty())
+    return getEmptySet();
+
+  return makePersistent(std::move(Result));
+}
+
+RangeSet RangeSet::Factory::intersect(RangeSet LHS, RangeSet RHS) {
+  // Shortcut: let's see if the intersection is even possible.
+  if (LHS.isEmpty() || RHS.isEmpty() || LHS.getMaxValue() < RHS.getMinValue() ||
+      RHS.getMaxValue() < LHS.getMinValue())
+    return getEmptySet();
+
+  return intersect(*LHS.Impl, *RHS.Impl);
+}
+
+RangeSet RangeSet::Factory::intersect(RangeSet LHS, llvm::APSInt Point) {
+  if (LHS.containsImpl(Point))
+    return getSet(ValueFactory.getValue(Point));
+
+  return getEmptySet();
+}
 
-  if (isEmpty())
-    return newRanges;
+RangeSet RangeSet::Factory::negate(RangeSet What) {
+  if (What.isEmpty())
+    return getEmptySet();
 
-  const llvm::APSInt sampleValue = getMinValue();
-  const llvm::APSInt &MIN = BV.getMinValue(sampleValue);
-  const llvm::APSInt &MAX = BV.getMaxValue(sampleValue);
+  ContainerType Result;
+  Result.reserve(What.size());
+
+  const llvm::APSInt SampleValue = What.getMinValue();
+  const llvm::APSInt &MIN = ValueFactory.getMinValue(SampleValue);
+  const llvm::APSInt &MAX = ValueFactory.getMaxValue(SampleValue);
 
   // Handle a special case for MIN value.
-  iterator i = begin();
-  const llvm::APSInt &from = i->From();
-  const llvm::APSInt &to = i->To();
-  if (from == MIN) {
-    // If [from, to] are [MIN, MAX], then just return the same [MIN, MAX].
-    if (to == MAX) {
-      newRanges = ranges;
+  iterator It = What.begin();
+  iterator End = What.end();
+
+  const llvm::APSInt &From = It->From();
+  const llvm::APSInt &To = It->To();
+
+  if (From == MIN) {
+    // If [From, To] are [MIN, MAX], then just return the same [MIN, MAX].
+    if (To == MAX) {
+      Result.insert(Result.end(), What.begin(), What.end());
+      return makePersistent(std::move(Result));
+    }
+
+    iterator Last = std::prev(End);
+
+    // Try to find and unite the following ranges:
+    // [MIN, MIN] & [MIN + 1, N] => [MIN, N].
+    if (Last->To() == MAX) {
+      // It means that in the original range we have ranges
+      //   [MIN, A], ... , [B, MAX]
+      // And the result should be [MIN, -B], ..., [-A, MAX]
+      Result.push_back(Range(MIN, ValueFactory.getValue(-Last->From())));
+      // We already negated Last, so we can skip it.
+      End = Last;
     } else {
-      // Add separate range for the lowest value.
-      newRanges = F.add(newRanges, Range(MIN, MIN));
-      // Skip adding the second range in case when [from, to] are [MIN, MIN].
-      if (to != MIN) {
-        newRanges = F.add(newRanges, Range(BV.getValue(-to), MAX));
-      }
+      // Add a separate range for the lowest value.
+      Result.push_back(Range(MIN, MIN));
+
+    // Skip adding the second range in case when [From, To] are [MIN, MIN].
+    if (To != MIN) {
+      Result.push_back(Range(ValueFactory.getValue(-To), MAX));
     }
+
     // Skip the first range in the loop.
-    ++i;
+    ++It;
   }
 
   // Negate all other ranges.
-  for (iterator e = end(); i != e; ++i) {
+  for (; It != End; ++It) {
     // Negate int values.
-    const llvm::APSInt &newFrom = BV.getValue(-i->To());
-    const llvm::APSInt &newTo = BV.getValue(-i->From());
+    const llvm::APSInt &NewFrom = ValueFactory.getValue(-It->To());
+    const llvm::APSInt &NewTo = ValueFactory.getValue(-It->From());
+
     // Add a negated range.
-    newRanges = F.add(newRanges, Range(newFrom, newTo));
+    Result.push_back(Range(NewFrom, NewTo));
   }
 
-  if (newRanges.isSingleton())
-    return newRanges;
-
-  // Try to find and unite next ranges:
-  // [MIN, MIN] & [MIN + 1, N] => [MIN, N].
-  iterator iter1 = newRanges.begin();
-  iterator iter2 = std::next(iter1);
-
-  if (iter1->To() == MIN && (iter2->From() - 1) == MIN) {
-    const llvm::APSInt &to = iter2->To();
-    // remove adjacent ranges
-    newRanges = F.remove(newRanges, *iter1);
-    newRanges = F.remove(newRanges, *newRanges.begin());
-    // add united range
-    newRanges = F.add(newRanges, Range(MIN, to));
-  }
+  llvm::sort(Result);
+  return makePersistent(std::move(Result));
 
-  return newRanges;
-}
+RangeSet RangeSet::Factory::deletePoint(const llvm::APSInt &Point,
+                                        RangeSet From) {
+  if (!From.contains(Point))
+    return From;
 
-RangeSet RangeSet::Delete(BasicValueFactory &BV, Factory &F,
-                          const llvm::APSInt &Point) const {
   llvm::APSInt Upper = Point;
   llvm::APSInt Lower = Point;
 
   ++Upper;
   --Lower;
 
   // Notice that the lower bound is greater than the upper bound.
-  return Intersect(BV, F, Upper, Lower);
+  return intersect(From, Upper, Lower);
+}
+
+void Range::print(raw_ostream &os) const {
+  os << '[' << From().toString(10) << ", " << To().toString(10) << ']';
 }
 
 void RangeSet::print(raw_ostream &os) const {
   bool isFirst = true;
   os << "{ ";
   for (iterator i = begin(), e = end(); i != e; ++i) {
     if (isFirst)
       isFirst = false;
     else
       os << ", ";
 
-    os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
-       << ']';
+    i->print(os);
   }
   os << " }";
 }
 
 REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(SymbolSet, SymbolRef)
 
 namespace {
 class EquivalenceClass;
 } // end anonymous namespace
 
 REGISTER_MAP_WITH_PROGRAMSTATE(ClassMap, SymbolRef, EquivalenceClass)
 REGISTER_MAP_WITH_PROGRAMSTATE(ClassMembers, EquivalenceClass, SymbolSet)
 REGISTER_MAP_WITH_PROGRAMSTATE(ConstraintRange, EquivalenceClass, RangeSet)

 }
 
 template <class... RestTy>
 LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory &BV,
                                          RangeSet::Factory &F, RangeSet Head,
                                          RangeSet Second, RestTy... Tail) {
   // Here we call either the <RangeSet,RangeSet,...> or <RangeSet,...> version
   // of the function and can be sure that the result is RangeSet.
-  return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...);
+  return intersect(BV, F, F.intersect(Head, Second), Tail...);
 }
 
 template <class SecondTy, class... RestTy>
 LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory &BV,
                                          RangeSet::Factory &F, RangeSet Head,
                                          SecondTy Second, RestTy... Tail) {
   if (Second) {
     // Here we call the <RangeSet,RangeSet,...> version of the function...
Range getSymmetricalRange(Range Origin, QualType T) {
 
     // Intersection is guaranteed to be non-empty.
     return {ValueFactory.getValue(-AbsMax), ValueFactory.getValue(AbsMax)};
   }
 
   /// Return a range set subtracting zero from \p Domain.
   RangeSet assumeNonZero(RangeSet Domain, QualType T) {
     APSIntType IntType = ValueFactory.getAPSIntType(T);
-    return Domain.Delete(ValueFactory, RangeFactory, IntType.getZeroValue());
+    return RangeFactory.deletePoint(IntType.getZeroValue(), Domain);
   }
 
   // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to
   //        obtain the negated symbolic expression instead of constructing the
   //        symbol manually. This will allow us to support finding ranges of not
   //        only negated SymSymExpr-type expressions, but also of other, simpler
   //        expressions which we currently do not know how to negate.
   Optional<RangeSet> getRangeForNegatedSub(SymbolRef Sym) {
     if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
       if (SSE->getOpcode() == BO_Sub) {
         QualType T = Sym->getType();
 
         // Do not negate unsigned ranges
         if (!T->isUnsignedIntegerOrEnumerationType() &&
             !T->isSignedIntegerOrEnumerationType())
           return llvm::None;
 
         SymbolManager &SymMgr = State->getSymbolManager();
         SymbolRef NegatedSym =
             SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T);
 
         if (const RangeSet *NegatedRange = getConstraint(State, NegatedSym)) {
-          return NegatedRange->Negate(ValueFactory, RangeFactory);
+          return RangeFactory.negate(*NegatedRange);
         }
       }
     }
     return llvm::None;
   }
 
   // Returns ranges only for binary comparison operators (except <=>)
   // when left and right operands are symbolic values.

 
 //===----------------------------------------------------------------------===//
 //                  Constraint manager implementation details
 //===----------------------------------------------------------------------===//
 
 class RangeConstraintManager : public RangedConstraintManager {
 public:
   RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB)
-      : RangedConstraintManager(EE, SVB) {}
+      : RangedConstraintManager(EE, SVB), F(getBasicVals()) {}
 
   //===------------------------------------------------------------------===//
   // Implementation for interface from ConstraintManager.
   //===------------------------------------------------------------------===//
 
   bool haveEqualConstraints(ProgramStateRef S1,
                             ProgramStateRef S2) const override {
     // NOTE: ClassMembers are as simple as back pointers for ClassMap,
LLVM_NODISCARD inline ProgramStateRef setConstraint(ProgramStateRef State,
 
     // There is a chance that we might need to update constraints for the
     // classes that are known to be disequal to Class.
     //
     // In order for this to be even possible, the new constraint should
     // be simply a constant because we can't reason about range disequalities.
     if (const llvm::APSInt *Point = Constraint.getConcreteValue())
       for (EquivalenceClass DisequalClass : Class.getDisequalClasses(State)) {
-        RangeSet UpdatedConstraint =
-            getRange(State, DisequalClass).Delete(getBasicVals(), F, *Point);
+        RangeSet UpdatedConstraint = getRange(State, DisequalClass);
+        UpdatedConstraint = F.deletePoint(*Point, UpdatedConstraint);
         Constraints = CF.add(Constraints, DisequalClass, UpdatedConstraint);
       }
 
     return State->set<ConstraintRange>(Constraints);
   }
 
   LLVM_NODISCARD inline ProgramStateRef
   setConstraint(ProgramStateRef State, SymbolRef Sym, RangeSet Constraint) {
inline void EquivalenceClass::addToDisequalityInfo(
   //    So, if Second == 10, it means that First != 10.
   //    At the same time, the same logic does not apply to ranges.
   if (const RangeSet *SecondConstraint = Constraints.lookup(Second))
     if (const llvm::APSInt *Point = SecondConstraint->getConcreteValue()) {
 
       RangeSet FirstConstraint = SymbolicRangeInferrer::inferRange(
           VF, RF, State, First.getRepresentativeSymbol());
 
-      FirstConstraint = FirstConstraint.Delete(VF, RF, *Point);
+      FirstConstraint = RF.deletePoint(*Point, FirstConstraint);
       Constraints = CRF.add(Constraints, First, FirstConstraint);
     }
 }
 
 inline Optional<bool> EquivalenceClass::areEqual(ProgramStateRef State,
                                                  SymbolRef FirstSym,
                                                  SymbolRef SecondSym) {
   EquivalenceClass First = find(State, FirstSym);
ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State,
   if (const llvm::APSInt *Value = Ranges->getConcreteValue())
     return *Value == 0;
 
   BasicValueFactory &BV = getBasicVals();
   APSIntType IntType = BV.getAPSIntType(Sym->getType());
   llvm::APSInt Zero = IntType.getZeroValue();
 
   // Check if zero is in the set of possible values.
-  if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty())
+  if (!Ranges->contains(Zero))
     return false;
 
   // Zero is a possible value, but it is not the /only/ possible value.
   return ConditionTruthVal();
 }
 
 const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St,
                                                       SymbolRef Sym) const {
RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym,
                                     const llvm::APSInt &Adjustment) {
   // Before we do any real work, see if the value can even show up.
   APSIntType AdjustmentType(Adjustment);
   if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
     return St;
 
   llvm::APSInt Point = AdjustmentType.convert(Int) - Adjustment;
 
-  RangeSet New = getRange(St, Sym).Delete(getBasicVals(), F, Point);
+  RangeSet New = getRange(St, Sym);
+  New = F.deletePoint(Point, New);
 
   if (New.isEmpty())
     // this is infeasible assumption
     return nullptr;
 
   ProgramStateRef NewState = setConstraint(St, Sym, New);
   return trackNE(NewState, Sym, Int, Adjustment);
 }
 
 ProgramStateRef
 RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym,
                                     const llvm::APSInt &Int,
                                     const llvm::APSInt &Adjustment) {
   // Before we do any real work, see if the value can even show up.
   APSIntType AdjustmentType(Adjustment);
   if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
     return nullptr;
 
   // [Int-Adjustment, Int-Adjustment]
   llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
-  RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt);
+  RangeSet New = getRange(St, Sym);
+  New = F.intersect(New, AdjInt);
 
   if (New.isEmpty())
     // this is infeasible assumption
     return nullptr;
 
   ProgramStateRef NewState = setConstraint(St, Sym, New);
   return trackEQ(NewState, Sym, Int, Adjustment);
 }
RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St,
   llvm::APSInt Min = AdjustmentType.getMinValue();
   if (ComparisonVal == Min)
     return F.getEmptySet();
 
   llvm::APSInt Lower = Min - Adjustment;
   llvm::APSInt Upper = ComparisonVal - Adjustment;
   --Upper;
 
-  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
+  RangeSet Result = getRange(St, Sym);
+  return F.intersect(Result, Lower, Upper);
 }
 
 ProgramStateRef
 RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym,
                                     const llvm::APSInt &Int,
                                     const llvm::APSInt &Adjustment) {
   RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
   return New.isEmpty() ? nullptr : setConstraint(St, Sym, New);
RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St,
   llvm::APSInt Max = AdjustmentType.getMaxValue();
   if (ComparisonVal == Max)
     return F.getEmptySet();
 
   llvm::APSInt Lower = ComparisonVal - Adjustment;
   llvm::APSInt Upper = Max - Adjustment;
   ++Lower;
 
-  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
+  RangeSet SymRange = getRange(St, Sym);
+  return F.intersect(SymRange, Lower, Upper);
 }
 
 ProgramStateRef
 RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym,
                                     const llvm::APSInt &Int,
                                     const llvm::APSInt &Adjustment) {
   RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
   return New.isEmpty() ? nullptr : setConstraint(St, Sym, New);
RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St,
   llvm::APSInt Min = AdjustmentType.getMinValue();
   if (ComparisonVal == Min)
     return getRange(St, Sym);
 
   llvm::APSInt Max = AdjustmentType.getMaxValue();
   llvm::APSInt Lower = ComparisonVal - Adjustment;
   llvm::APSInt Upper = Max - Adjustment;
 
-  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
+  RangeSet SymRange = getRange(St, Sym);
+  return F.intersect(SymRange, Lower, Upper);
 }
 
 ProgramStateRef
 RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym,
                                     const llvm::APSInt &Int,
                                     const llvm::APSInt &Adjustment) {
   RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
   return New.isEmpty() ? nullptr : setConstraint(St, Sym, New);
RangeConstraintManager::getSymLERange(llvm::function_ref<RangeSet()> RS,
   llvm::APSInt Max = AdjustmentType.getMaxValue();
   if (ComparisonVal == Max)
     return RS();
 
   llvm::APSInt Min = AdjustmentType.getMinValue();
   llvm::APSInt Lower = Min - Adjustment;
   llvm::APSInt Upper = ComparisonVal - Adjustment;
 
-  return RS().Intersect(getBasicVals(), F, Lower, Upper);
+  RangeSet Default = RS();
+  return F.intersect(Default, Lower, Upper);
 }
 
 RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St,
                                                SymbolRef Sym,
                                                const llvm::APSInt &Int,
                                                const llvm::APSInt &Adjustment) {
   return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment);
 }
ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange(
   return Out.isEmpty() ? nullptr : setConstraint(State, Sym, Out);
 }
 
 ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(
     ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
     const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
   RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
   RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
-  RangeSet New(RangeLT.addRange(F, RangeGT));
+  RangeSet New(F.add(RangeLT, RangeGT));
   return New.isEmpty() ? nullptr : setConstraint(State, Sym, New);
 }
 
 //===----------------------------------------------------------------------===//
 // Pretty-printing.
 //===----------------------------------------------------------------------===//
 
 void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State,

clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp

if (Op == BO_Add || Op == BO_Sub) {
       // subtracted is, say, CHAR_MIN, and the promoted type is 'int'.
       if (Op == BO_Sub)
         Adjustment = -Adjustment;
     }
   }
 }
 
 } // end of namespace ento
-
 } // end of namespace clang

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

 //===- unittests/StaticAnalyzer/RangeSetTest.cpp ----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Basic/Builtins.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h"
 #include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/APSInt.h"
+#include "llvm/Support/raw_ostream.h"
+#include "gtest/gtest-typed-test.h"
 #include "gtest/gtest.h"
 
+using namespace clang;
+using namespace ento;
+
 namespace clang {
 namespace ento {
-namespace {
 
-// TestCase contains to lists of ranges.
-// Original one has to be negated.
-// Expected one has to be compared to negated original range.
-template <typename T> struct TestCase {
-  RangeSet original;
-  RangeSet expected;
-
-  TestCase(BasicValueFactory &BVF, RangeSet::Factory &F,
-           const std::initializer_list<T> &originalList,
-           const std::initializer_list<T> &expectedList)
-      : original(createRangeSetFromList(BVF, F, originalList)),
-        expected(createRangeSetFromList(BVF, F, expectedList)) {}
-
-private:
-  RangeSet createRangeSetFromList(BasicValueFactory &BVF, RangeSet::Factory &F,
-                                  const std::initializer_list<T> rangeList) {
-    llvm::APSInt from(sizeof(T) * 8, std::is_unsigned<T>::value);
-    llvm::APSInt to = from;
-    RangeSet rangeSet = F.getEmptySet();
-    for (auto it = rangeList.begin(); it != rangeList.end(); it += 2) {
-      from = *it;
-      to = *(it + 1);
-      rangeSet = rangeSet.addRange(
-          F, RangeSet(F, BVF.getValue(from), BVF.getValue(to)));
-    }
-    return rangeSet;
-  }
-
-  void printNegate(const TestCase &TestCase) {
-    TestCase.original.print(llvm::dbgs());
-    llvm::dbgs() << " => ";
-    TestCase.expected.print(llvm::dbgs());
-  }
-};
+template <class RangeOrSet> static std::string toString(const RangeOrSet &Obj) {
+  std::string ObjRepresentation;
+  llvm::raw_string_ostream SS(ObjRepresentation);
+  Obj.print(SS);
+  return SS.str();
+LLVM_ATTRIBUTE_UNUSED static std::string toString(const llvm::APSInt &Point) {
+  return Point.toString(10);
+}
+// We need it here for better fail diagnostics from gtest.
+LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS,
+                                                      const RangeSet &Set) {
+  return OS << toString(Set);
+}
+
+} // namespace ento
+} // namespace clang
+
+namespace {
 
-class RangeSetTest : public testing::Test {
-protected:
+template <typename BaseType> class RangeSetTest : public testing::Test {
+public:
   // Init block
   std::unique_ptr<ASTUnit> AST = tooling::buildASTFromCode("struct foo;");
-  ASTContext &context = AST->getASTContext();
-  llvm::BumpPtrAllocator alloc;
-  BasicValueFactory BVF{context, alloc};
-  RangeSet::Factory F;
+  ASTContext &Context = AST->getASTContext();
+  llvm::BumpPtrAllocator Arena;
+  BasicValueFactory BVF{Context, Arena};
+  RangeSet::Factory F{BVF};
   // End init block
 
-  template <typename T> void checkNegate() {
-    using type = T;
+  using Self = RangeSetTest<BaseType>;
+  using RawRange = std::pair<BaseType, BaseType>;
+  using RawRangeSet = std::initializer_list<RawRange>;
+
+  static constexpr BaseType getMin() {
+    return std::numeric_limits<BaseType>::min();
+  }
+  static constexpr BaseType getMax() {
+    return std::numeric_limits<BaseType>::max();
+  }
+  static constexpr BaseType getMid() {
+    return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
+  }
+
+  static constexpr bool isSigned() { return std::is_signed<BaseType>::value; }
+  static constexpr BaseType fromInt(int X) { return static_cast<BaseType>(X); }
+
+  static llvm::APSInt Base;
+  const llvm::APSInt &from(BaseType X) {
+    llvm::APSInt Dummy = Base;
+    Dummy = X;
+    return BVF.getValue(Dummy);
+  }
+
+  Range from(const RawRange &Init) {
+    return Range(from(Init.first), from(Init.second));
+  }
+
+  RangeSet from(const RawRangeSet &Init) {
+    RangeSet RangeSet = F.getEmptySet();
+    for (const auto &Raw : Init) {
+      RangeSet = F.add(RangeSet, from(Raw));
+    }
+    return RangeSet;
+  }
+
+  template <class F, class... RawArgTypes>
+  void wrap(F ActualFunction, RawArgTypes &&...Args) {
+    (this->*ActualFunction)(from(std::forward<RawArgTypes>(Args))...);
+  }
+
+  void checkNegateImpl(RangeSet Original, RangeSet Expected) {
+    RangeSet NegatedFromOriginal = F.negate(Original);
+    EXPECT_EQ(NegatedFromOriginal, Expected);
+    // Negate negated back and check with original.
+    RangeSet NegatedBackward = F.negate(NegatedFromOriginal);
+    EXPECT_EQ(NegatedBackward, Original);
+  }
+
+  void checkNegate(RawRangeSet RawOriginal, RawRangeSet RawExpected) {
+    wrap(&Self::checkNegateImpl, RawOriginal, RawExpected);
+  }
+
+  template <class PointOrSet>
+  void checkIntersectImpl(RangeSet LHS, PointOrSet RHS, RangeSet Expected) {
+    RangeSet Result = F.intersect(LHS, RHS);
+    EXPECT_EQ(Result, Expected)
+        << "while intersecting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkIntersectRangeImpl(RangeSet LHS, const llvm::APSInt &Lower,
+                               const llvm::APSInt &Upper, RangeSet Expected) {
+    RangeSet Result = F.intersect(LHS, Lower, Upper);
+    EXPECT_EQ(Result, Expected)
+        << "while intersecting " << toString(LHS) << " and [" << toString(Lower)
+        << ", " << toString(Upper) << "]";
+  }
+
+  void checkIntersect(RawRangeSet RawLHS, RawRangeSet RawRHS,
+                      RawRangeSet RawExpected) {
+    wrap(&Self::checkIntersectImpl<RangeSet>, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkIntersect(RawRangeSet RawLHS, BaseType RawRHS,
+                      RawRangeSet RawExpected) {
+    wrap(&Self::checkIntersectImpl<const llvm::APSInt &>, RawLHS, RawRHS,
+         RawExpected);
+  }
+
+  void checkIntersect(RawRangeSet RawLHS, BaseType RawLower, BaseType RawUpper,
+                      RawRangeSet RawExpected) {
+    wrap(&Self::checkIntersectRangeImpl, RawLHS, RawLower, RawUpper,
+         RawExpected);
+  }
+
+  void checkContainsImpl(RangeSet LHS, const llvm::APSInt &RHS, bool Expected) {
+    bool Result = LHS.contains(RHS);
+    EXPECT_EQ(Result, Expected)
+        << toString(LHS) << (Result ? " contains " : " doesn't contain ")
+        << toString(RHS);
+  }
+
+  void checkContains(RawRangeSet RawLHS, BaseType RawRHS, bool Expected) {
+    checkContainsImpl(from(RawLHS), from(RawRHS), Expected);
+  }
+
+  template <class RHSType>
+  void checkAddImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+    RangeSet Result = F.add(LHS, RHS);
+    EXPECT_EQ(Result, Expected)
+        << "while adding " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkAdd(RawRangeSet RawLHS, RawRange RawRHS, RawRangeSet RawExpected) {
+    wrap(&Self::checkAddImpl<Range>, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
+                RawRangeSet RawExpected) {
+    wrap(&Self::checkAddImpl<RangeSet>, RawRHS, RawLHS, RawExpected);
+  }
+
+  void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
+                       RangeSet Expected) {
+    RangeSet Result = F.deletePoint(Point, From);
+    EXPECT_EQ(Result, Expected)
+        << "while deleting " << toString(Point) << " from " << toString(From);
+  }
+
+  void checkDelete(BaseType Point, RawRangeSet RawFrom,
+                   RawRangeSet RawExpected) {
+    wrap(&Self::checkDeleteImpl, Point, RawFrom, RawExpected);
+  }
+};
 
-    // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
+} // namespace
+
+template <typename BaseType>
+llvm::APSInt RangeSetTest<BaseType>::Base{sizeof(BaseType) * 8, !isSigned()};
+
+using IntTypes = ::testing::Types<int8_t, uint8_t, int16_t, uint16_t, int32_t,
+                                  uint32_t, int64_t, uint64_t>;
+TYPED_TEST_CASE(RangeSetTest, IntTypes);
+
+TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
 
-    // MID is a value in the middle of the range
-    // which unary minus does not affect on,
-    // e.g. int8/int32(0), uint8(128), uint32(2147483648).
-
-    constexpr type MIN = std::numeric_limits<type>::min();
-    constexpr type MAX = std::numeric_limits<type>::max();
-    constexpr type MID = std::is_signed<type>::value
-                             ? 0
-                             : ~(static_cast<type>(-1) / static_cast<type>(2));
-    constexpr type A = MID - static_cast<type>(42 + 42);
-    constexpr type B = MID - static_cast<type>(42);
-    constexpr type C = -B;
-    constexpr type D = -A;
+  constexpr TypeParam MIN = TestFixture::getMin();
+  constexpr TypeParam MAX = TestFixture::getMax();
+  constexpr TypeParam MID = TestFixture::getMid();
+  constexpr TypeParam A = MID - TestFixture::fromInt(42 + 42);
+  constexpr TypeParam B = MID - TestFixture::fromInt(42);
+  constexpr TypeParam C = -B;
+  constexpr TypeParam D = -A;
 
-    static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
-                  "Values shall be in an ascending order");
 
-    // Left {[x, y], [x, y]} is what shall be negated.
-    // Right {[x, y], [x, y]} is what shall be compared to a negation result.
-    TestCase<type> cases[] = {
-        {BVF, F, {MIN, A}, {MIN, MIN, D, MAX}},
-        {BVF, F, {MIN, C}, {MIN, MIN, B, MAX}},
-        {BVF, F, {MIN, MID}, {MIN, MIN, MID, MAX}},
-        {BVF, F, {MIN, MAX}, {MIN, MAX}},
-        {BVF, F, {A, D}, {A, D}},
-        {BVF, F, {A, B}, {C, D}},
-        {BVF, F, {MIN, A, D, MAX}, {MIN, A, D, MAX}},
-        {BVF, F, {MIN, B, MID, D}, {MIN, MIN, A, MID, C, MAX}},
-        {BVF, F, {MIN, MID, C, D}, {MIN, MIN, A, B, MID, MAX}},
-        {BVF, F, {MIN, MID, C, MAX}, {MIN, B, MID, MAX}},
-        {BVF, F, {A, MID, D, MAX}, {MIN + 1, A, MID, D}},
-        {BVF, F, {A, A}, {D, D}},
-        {BVF, F, {MID, MID}, {MID, MID}},
-        {BVF, F, {MAX, MAX}, {MIN + 1, MIN + 1}},
-    };
+  this->checkNegate({{MIN, A}}, {{MIN, MIN}, {D, MAX}});
+  this->checkNegate({{MIN, C}}, {{MIN, MIN}, {B, MAX}});
+  this->checkNegate({{MIN, MID}}, {{MIN, MIN}, {MID, MAX}});
+  this->checkNegate({{MIN, MAX}}, {{MIN, MAX}});
+  this->checkNegate({{A, D}}, {{A, D}});
+  this->checkNegate({{A, B}}, {{C, D}});
+  this->checkNegate({{MIN, A}, {D, MAX}}, {{MIN, A}, {D, MAX}});
+  this->checkNegate({{MIN, B}, {MID, D}}, {{MIN, MIN}, {A, MID}, {C, MAX}});
+  this->checkNegate({{MIN, MID}, {C, D}}, {{MIN, MIN}, {A, B}, {MID, MAX}});
+  this->checkNegate({{MIN, MID}, {C, MAX}}, {{MIN, B}, {MID, MAX}});
+  this->checkNegate({{A, MID}, {D, MAX}}, {{MIN + 1, A}, {MID, D}});
+  this->checkNegate({{A, A}}, {{D, D}});
+  this->checkNegate({{MID, MID}}, {{MID, MID}});
+  this->checkNegate({{MAX, MAX}}, {{MIN + 1, MIN + 1}});
+}
 
-    for (const auto &c : cases) {
-      // Negate original and check with expected.
-      RangeSet negatedFromOriginal = c.original.Negate(BVF, F);
-      EXPECT_EQ(negatedFromOriginal, c.expected);
-      // Negate negated back and check with original.
-      RangeSet negatedBackward = negatedFromOriginal.Negate(BVF, F);
-      EXPECT_EQ(negatedBackward, c.original);
-    }
-  }
-};
+TYPED_TEST(RangeSetTest, RangeSetPointIntersectTest) {
+  // Check that we can correctly intersect empty sets.
+  this->checkIntersect({}, 42, {});
+  // Check that intersection with itself produces the same set.
+  this->checkIntersect({{42, 42}}, 42, {{42, 42}});
+  // Check more general cases.
+  this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 42, {});
+  this->checkIntersect({{0, 10}, {20, 30}, {30, 60}}, 42, {{42, 42}});
+}
+
+TYPED_TEST(RangeSetTest, RangeSetRangeIntersectTest) {
+  constexpr TypeParam MIN = TestFixture::getMin();
+  constexpr TypeParam MAX = TestFixture::getMax();
+
+  // Check that we can correctly intersect empty sets.
+  this->checkIntersect({}, 10, 20, {});
+  this->checkIntersect({}, 20, 10, {});
+  // Check that intersection with itself produces the same set.
+  this->checkIntersect({{10, 20}}, 10, 20, {{10, 20}});
+  this->checkIntersect({{MIN, 10}, {20, MAX}}, 20, 10, {{MIN, 10}, {20, MAX}});
+  // Check non-overlapping range intersections.
+  this->checkIntersect({{10, 20}}, 21, 9, {});
+  this->checkIntersect({{MIN, 9}, {21, MAX}}, 10, 20, {});
+  // Check more general cases.
+  this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 10, 35,
+                       {{10, 10}, {20, 30}, {30, 35}});
+  this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 35, 10,
+                       {{0, 10}, {35, 40}, {50, 60}});
+
+TYPED_TEST(RangeSetTest, RangeSetGenericIntersectTest) {
+  // Check that we can correctly intersect empty sets.
+  this->checkIntersect({}, {}, {});
+  this->checkIntersect({}, {{0, 10}}, {});
+  this->checkIntersect({{0, 10}}, {}, {});
+
+  this->checkIntersect({{0, 10}}, {{4, 6}}, {{4, 6}});
+  this->checkIntersect({{0, 10}}, {{4, 20}}, {{4, 10}});
+  // Check that intersection with points works as expected.
+  this->checkIntersect({{0, 10}}, {{4, 4}}, {{4, 4}});
+  // All ranges are closed, check that intersection with edge points works as
+  // expected.
+  this->checkIntersect({{0, 10}}, {{10, 10}}, {{10, 10}});
+
+  // Let's check that we can skip some intervals and partially intersect
+  // other intervals.
+  this->checkIntersect({{0, 2}, {4, 5}, {6, 9}, {10, 11}, {12, 12}, {13, 15}},
+                       {{8, 14}, {20, 30}},
+                       {{8, 9}, {10, 11}, {12, 12}, {13, 14}});
+  // Check more generic case.
+  this->checkIntersect(
+      {{0, 1}, {2, 3}, {5, 6}, {7, 15}, {25, 30}},
+      {{4, 10}, {11, 11}, {12, 16}, {17, 17}, {19, 20}, {21, 23}, {24, 27}},
+      {{5, 6}, {7, 10}, {11, 11}, {12, 15}, {25, 27}});
 
-TEST_F(RangeSetTest, RangeSetNegateTest) {
-  checkNegate<int8_t>();
-  checkNegate<uint8_t>();
-  checkNegate<int16_t>();
-  checkNegate<uint16_t>();
-  checkNegate<int32_t>();
-  checkNegate<uint32_t>();
-  checkNegate<int64_t>();
-  checkNegate<uint64_t>();
+TYPED_TEST(RangeSetTest, RangeSetContainsTest) {
+  // Check with an empty set.
+  this->checkContains({}, 10, false);
+  // Check contains with sets of size one:
+  //   * when the whole range is less
+  this->checkContains({{0, 5}}, 10, false);
+  //   * when the whole range is greater
+  this->checkContains({{20, 25}}, 10, false);
+  //   * when the range is just the point we are looking for
+  this->checkContains({{10, 10}}, 10, true);
+  //   * when the range starts with the point
+  this->checkContains({{10, 15}}, 10, true);
+  //   * when the range ends with the point
+  this->checkContains({{5, 10}}, 10, true);
+  //   * when the range has the point somewhere in the middle
+  this->checkContains({{0, 25}}, 10, true);
+  // Check similar cases, but with larger sets.
+  this->checkContains({{0, 5}, {10, 10}, {15, 20}}, 10, true);
+  this->checkContains({{0, 5}, {10, 12}, {15, 20}}, 10, true);
+  this->checkContains({{0, 5}, {5, 7}, {8, 10}, {12, 41}}, 10, true);
+
+  constexpr TypeParam MIN = TestFixture::getMin();
+  constexpr TypeParam MAX = TestFixture::getMax();
+  constexpr TypeParam MID = TestFixture::getMid();
+  this->checkContains({{MIN, MAX}}, 0, true);
+  this->checkContains({{MIN, MAX}}, MID, true);
+  this->checkContains({{MIN, MAX}}, -10, true);
+  this->checkContains({{MIN, MAX}}, 10, true);
 }
 
-} // namespace
-} // namespace ento
-} // namespace clang
+TYPED_TEST(RangeSetTest, RangeSetAddTest) {
+  // Check adding single ranges.
+  this->checkAdd({}, {10, 20}, {{10, 20}});
+  this->checkAdd({{0, 5}}, {10, 20}, {{0, 5}, {10, 20}});
+  this->checkAdd({{0, 5}, {30, 40}}, {10, 20}, {{0, 5}, {10, 20}, {30, 40}});
+
+  // Check adding whole sets of ranges.
+  this->checkAdd({{0, 5}}, {{10, 20}}, {{0, 5}, {10, 20}});
+  // Check that ordering of ranges is as expected.
+  this->checkAdd({{0, 5}, {30, 40}}, {{10, 20}}, {{0, 5}, {10, 20}, {30, 40}});
+  this->checkAdd({{0, 5}, {30, 40}}, {{10, 20}, {50, 60}},
+                 {{0, 5}, {10, 20}, {30, 40}, {50, 60}});
+  this->checkAdd({{10, 20}, {50, 60}}, {{0, 5}, {30, 40}, {70, 80}},
+                 {{0, 5}, {10, 20}, {30, 40}, {50, 60}, {70, 80}});
+}
+
+TYPED_TEST(RangeSetTest, RangeSetDeletePointTest) {
+  constexpr TypeParam MIN = TestFixture::getMin();
+  constexpr TypeParam MAX = TestFixture::getMax();
+  constexpr TypeParam MID = TestFixture::getMid();
+
+  this->checkDelete(MID, {{MIN, MAX}}, {{MIN, MID - 1}, {MID + 1, MAX}});
+  // Check that delete works with an empty set.
+  this->checkDelete(10, {}, {});
+  // Check that delete can remove entire ranges.
+  this->checkDelete(10, {{10, 10}}, {});
+  this->checkDelete(10, {{0, 5}, {10, 10}, {20, 30}}, {{0, 5}, {20, 30}});
+  // Check that delete can split existing ranges into two.
+  this->checkDelete(10, {{0, 5}, {7, 15}, {20, 30}},
+                    {{0, 5}, {7, 9}, {11, 15}, {20, 30}});
+  // Check that delete of the point not from the range set works as expected.
+  this->checkDelete(10, {{0, 5}, {20, 30}}, {{0, 5}, {20, 30}});
+}