[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

93

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

[vsavchenko]

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

93

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

93

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.

141

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

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

120

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.

285

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

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

211

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

93

Sounds reasonable, I'll give it a shot!

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

285

😊

clang/unittests/StaticAnalyzer/RangeSetTest.cpp

211

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

120

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

93

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

50

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

52–61

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

116

I think it should be std::size_t.

124–129

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

141

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?

155–166

I think an example would be awesome here.

176–180

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

196–199

201–202

209

As commented later, this function worth to be documented.

213–214

Why do we need to explicitly spell the RangeSet here?

216–217

219–221

228

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

231–234

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

266–273

Finally, we got this, awesome!

275–284

303–304

If we implement equality, we should also support inequality.

304–305

Missing explicit.

304–308

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.

306

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

151–154

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.

182–183

186–193

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

285

I agree. These are black magic. xD

326–329

It could definitely bear a longer name.

371–374

379

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.

388

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.

428–433

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]

436

494–495

Can we use range-based for loops?

[vsavchenko]

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

116

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.

124–129

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

155–166

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

176–180

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

196–199

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

201–202

+1

209

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.

213–214

Good point!

216–217

+1

219–221

+1

231–234

It is, and it is forgotten, good catch!

303–304

Sure!

304–305

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

306

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

151–154

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

182–183

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.

186–193

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

326–329

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?

371–374

OK

379

NP

388

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.

494–495

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

124–129

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

176–180

Thanks. BTW I just forgot about this comment :D

304–305

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

182–183

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.

326–329

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

52–61

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

141

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

304–305

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

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

326–329

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

50

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

52–61

Okay.

112

Shouldn't we call this const_iterator?

141

Makes sense.

211

213

287

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

290–299

Aww, excellent. Thanks.

304–305

Okay.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

326–329

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.

430

466–474

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

494–503

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

57

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

141

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

78–79

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.

135

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.

180

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}});

190

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

438–439

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

525

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

438–439

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

78–79

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.

211

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

213

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

466–474

Yeah, I'd say that it is wordier.

494–503

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.

190

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

191

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

494–503

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/ADT/APSInt.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 *> {
+class Range {
 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) : Impl(&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) : Range(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 &From() const { return *Impl.first; }
+  const llvm::APSInt &To() const { return *Impl.second; }
   const llvm::APSInt *getConcreteValue() const {
     return &From() == &To() ? &From() : nullptr;
   }
 
   void Profile(llvm::FoldingSetNodeID &ID) const {
     ID.AddPointer(&From());
     ID.AddPointer(&To());
   }
+  void dump(raw_ostream &OS) const;
+
+  // In order to keep non-overlapping ranges sorted, we can compare only From
+  // points.
+  bool operator<(const Range &RHS) const { return From() < RHS.From(); }
+
+  bool operator==(const Range &RHS) const { return Impl == RHS.Impl; }
+  bool operator!=(const Range &RHS) const { return !operator==(RHS); }
+
+private:
+  std::pair<const llvm::APSInt *, const llvm::APSInt *> Impl;
 };
 
-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.
+  //     Formerly it used to be llvm::ImmutableSet, which is 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 const_iterator = ImplType::const_iterator;
+
+  const_iterator begin() const { return Impl->begin(); }
+  const_iterator end() const { return Impl->end(); }
+  size_t size() const { return Impl->size(); }
 
-  RangeSet(PrimRangeSet RS) : ranges(RS) {}
+  bool isEmpty() const { return Impl->empty(); }
 
-  /// Create a new set with all ranges of this set and RS.
+  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.
+    ///
+    /// Complexity: O(N)
+    ///             where N = size(Original)
+    RangeSet add(RangeSet Original, Range Element);
+    /// Create a new set with all ranges from the original set plus the point.
     /// 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, const llvm::APSInt &Point);
+
+    RangeSet getEmptySet() { return &EmptySet; }
+
+    /// Create a new set with just one range.
+    /// @{
+    RangeSet getRangeSet(Range Origin);
+    RangeSet getRangeSet(const llvm::APSInt &From, const llvm::APSInt &To) {
+      return getRangeSet(Range(From, To));
     }
+    RangeSet getRangeSet(const llvm::APSInt &Origin) {
+      return getRangeSet(Origin, Origin);
+    }
+    /// @}
 
-  iterator begin() const { return ranges.begin(); }
-  iterator end() const { return ranges.end(); }
+    /// 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(RangeSet From, const llvm::APSInt &Point);
+    /// 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].
+    ///
+    /// Negate is a self-inverse function, i.e. negate(negate(R)) == R.
+    ///
+    /// Complexity: O(N)
+    ///             where N = size(What)
+    RangeSet negate(RangeSet What);
 
-  bool isEmpty() const { return ranges.isEmpty(); }
+  private:
+    /// Return a persistent version of the given container.
+    RangeSet makePersistent(ContainerType &&From);
+    /// Construct a new persistent version of the given container.
+    ContainerType *construct(ContainerType &&From);
+
+    RangeSet intersect(const ContainerType &LHS, const ContainerType &RHS);
+
+    // Many operations include 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 container 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;
+  };
 
-  /// 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;
+  ~RangeSet() = default;
+
+  /// Construct a new RangeSet representing '{ [From, To] }'.
+  RangeSet(Factory &F, const llvm::APSInt &From, const llvm::APSInt &To)
+      : RangeSet(F.getRangeSet(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.getRangeSet(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
+  /// Get the 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
+  /// Get the maximal value covered by the ranges in the set.
+  ///
+  /// Complexity: O(1)
   const llvm::APSInt &getMaxValue() const;
 
+  /// Test whether the given point is contained by any of the ranges.
+  ///
+  /// Complexity: O(logN)
+  ///             where N = size(this)
+  bool contains(llvm::APSInt Point) const { return containsImpl(Point); }
+
+  void dump(raw_ostream &OS) const;
+
+  bool operator==(const RangeSet &Other) const { return *Impl == *Other.Impl; }
+  bool operator!=(const RangeSet &Other) const { return !(*this == Other); }
+
 private:
-  void IntersectInRange(BasicValueFactory &BV, Factory &F,
-                        const llvm::APSInt &Lower, const llvm::APSInt &Upper,
-                        PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
-                        PrimRangeSet::iterator &e) const;
+  /* implicit */ RangeSet(ContainerType *RawContainer) : Impl(RawContainer) {}
+  /* implicit */ RangeSet(UnderlyingType Ptr) : Impl(Ptr) {}
 
+  /// Pin given points to the type represented by the current range set.
+  ///
+  /// This makes parameter points to be in-out parameters.
+  /// In order to maintain consistent types across all of the ranges in the set
+  /// and to keep all the operations to compare ONLY points of the same type, we
+  /// need to pin every point before any operation.
+  ///
+  /// @Returns true if the given points can be converted to the target type
+  ///          without changing the values (i.e. trivially) and false otherwise.
+  /// @{
   bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
+  bool pin(llvm::APSInt &Point) 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;
-
-  void print(raw_ostream &os) const;
+  // This version of this function modifies its arguments (pins it).
+  bool containsImpl(llvm::APSInt &Point) const;
 
-  bool operator==(const RangeSet &other) const {
-    return ranges == other.ranges;
-  }
+  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/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/Compiler.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);
+
+  const_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::add(RangeSet Original, const llvm::APSInt &Point) {
+  return add(Original, Range(Point));
 
-    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::getRangeSet(Range From) {
+  ContainerType Result;
+  Result.push_back(From);
+  return makePersistent(std::move(Result));
+}
+
+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);
+  const_iterator It = llvm::upper_bound(*this, Dummy);
+  if (It == begin())
+    return false;
+
+  return std::prev(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);
-    }
+  const_iterator First = LHS.begin(), Second = RHS.begin(),
+                 FirstEnd = LHS.end(), SecondEnd = RHS.end();
+
+  const auto SwapIterators = [&First, &FirstEnd, &Second, &SecondEnd]() {
+    std::swap(First, Second);
+    std::swap(FirstEnd, SecondEnd);
+  };
+
+  // If we ran out of ranges in one set, but not in 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())
+      SwapIterators();
+
+    // 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;
       }
 
-  return newRanges;
+      // We have a guaranteed intersection at this point!
+      // And this is the current situation:
+      //
+      //    ----[   First   ]----------------->
+      //    -------[ Second ------------------>
+      //
+      // 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.
+        SwapIterators();
       }
 
-// Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus
-// operation under the values of the type.
+      // At this point, we have the following 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 ]--[  Second+1 ---------->
       //
-// 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].
+      // We don't know the relationship between First->From and
+      // Second->From and we don't know whether Second+1 intersects
+      // with First.
       //
-// 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();
+      // 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+1
+      // because First->From <= Second->To < (Second+1)->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 getRangeSet(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);
+  const llvm::APSInt SampleValue = What.getMinValue();
+  const llvm::APSInt &MIN = ValueFactory.getMinValue(SampleValue);
+  const llvm::APSInt &MAX = ValueFactory.getMaxValue(SampleValue);
+
+  ContainerType Result;
+  Result.reserve(What.size() + (SampleValue == MIN));
 
   // 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;
+  const_iterator It = What.begin();
+  const_iterator End = What.end();
+
+  const llvm::APSInt &From = It->From();
+  const llvm::APSInt &To = It->To();
+
+  if (From == MIN) {
+    // If the range [From, To] is [MIN, MAX], then result is also [MIN, MAX].
+    if (To == MAX) {
+      return What;
+    }
+
+    const_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.emplace_back(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.emplace_back(MIN, MIN);
+
+    // Skip adding the second range in case when [From, To] are [MIN, MIN].
+    if (To != MIN) {
+      Result.emplace_back(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.emplace_back(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(RangeSet From,
+                                        const llvm::APSInt &Point) {
+  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 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)
-       << ']';
-  }
-  os << " }";
+void Range::dump(raw_ostream &OS) const {
+  OS << '[' << From().toString(10) << ", " << To().toString(10) << ']';
+
+void RangeSet::dump(raw_ostream &OS) const {
+  OS << "{ ";
+  llvm::interleaveComma(*this, OS, [&OS](const Range &R) { R.dump(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)
 
 REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(ClassSet, EquivalenceClass)
 REGISTER_MAP_WITH_PROGRAMSTATE(DisequalityMap, EquivalenceClass, ClassSet)
 
 namespace {
 /// This class encapsulates a set of symbols equal to each other.
 ///
 /// The main idea of the approach requiring such classes is in narrowing
 /// and sharing constraints between symbols within the class.  Also we can
 /// conclude that there is no practical need in storing constraints for
 /// every member of the class separately.
 ///
 /// Main terminology:
 ///
 ///   * "Equivalence class" is an object of this class, which can be efficiently
 ///     compared to other classes.  It represents the whole class without
 ///     storing the actual in it.  The members of the class however can be
 ///     retrieved from the state.
 ///
 ///   * "Class members" are the symbols corresponding to the class.  This means

 }
 
 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(Domain, IntType.getZeroValue());
   }
 
   // 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 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(UpdatedConstraint, *Point);
 
         // If we end up with at least one of the disequal classes to be
         // constrained with an empty range-set, the state is infeasible.
         if (UpdatedConstraint.isEmpty())
           return nullptr;
 
         Constraints = CF.add(Constraints, DisequalClass, UpdatedConstraint);
       }
inline bool 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(FirstConstraint, *Point);
 
       // If the First class is about to be constrained with an empty
       // range-set, the state is infeasible.
       if (FirstConstraint.isEmpty())
         return false;
 
       Constraints = CRF.add(Constraints, First, FirstConstraint);
     }
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(New, Point);
 
   return trackNE(New, St, 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);
 
   return trackEQ(New, St, Sym, Int, Adjustment);
 }
 
 RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St,
                                                SymbolRef Sym,
                                                const llvm::APSInt &Int,
                                                const llvm::APSInt &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 trackNE(New, St, Sym, Int, Adjustment);
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 trackNE(New, St, Sym, Int, Adjustment);
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,
for (SymbolRef ClassMember : ClassMembers) {
       if (First) {
         First = false;
       } else {
         Out << ',';
         Out << NL;
       }
       Indent(Out, Space, IsDot)
           << "{ \"symbol\": \"" << ClassMember << "\", \"range\": \"";
-      P.second.print(Out);
+      P.second.dump(Out);
       Out << "\" }";
     }
   }
   Out << NL;
 
   --Space;
   Indent(Out, Space, IsDot) << "]," << NL;
 }

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.dump(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 checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
+    wrap(&Self::checkAddImpl<const llvm::APSInt &>, RawLHS, RawRHS,
+         RawExpected);
+  }
+
+  void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
+                       RangeSet Expected) {
+    RangeSet Result = F.deletePoint(From, Point);
+    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 points
+  this->checkAdd({}, 10, {{10, 10}});
+  this->checkAdd({{0, 5}}, 10, {{0, 5}, {10, 10}});
+  this->checkAdd({{0, 5}, {30, 40}}, 10, {{0, 5}, {10, 10}, {30, 40}});
+
+  // 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}});
+}