[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

This revision was not accepted when it landed; it landed in state "Needs 
Review".
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.
Closed by commit rG6a399bf4b3aa: [analyzer] Implemented 
RangeSet::Factory::unite function to handle… (authored by ASDenysPetrov).

Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -35,12 +35,34 @@
   const RangeSet &Set) {
   return OS << toString(Set);
 }
+// We need it here for better fail diagnostics from gtest.
+LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS,
+  const Range &R) {
+  return OS << toString(R);
+}
 
 } // namespace ento
 } // namespace clang
 
 namespace {
 
+template  struct TestValues {
+  static constexpr T MIN = std::numeric_limits::min();
+  static constexpr T MAX = std::numeric_limits::max();
+  // 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).
+  static constexpr T MID =
+  std::is_signed::value ? 0 : ~(static_cast(-1) / static_cast(2));
+  static constexpr T A = MID - (MAX - MID) / 3 * 2;
+  static constexpr T B = MID - (MAX - MID) / 3;
+  static constexpr T C = -B;
+  static constexpr T D = -A;
+
+  static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+"Values shall be in an ascending order");
+};
+
 template  class RangeSetTest : public testing::Test {
 public:
   // Init block
@@ -55,24 +77,11 @@
   using RawRange = std::pair;
   using RawRangeSet = std::initializer_list;
 
-  static constexpr BaseType getMin() {
-return std::numeric_limits::min();
-  }
-  static constexpr BaseType getMax() {
-return std::numeric_limits::max();
-  }
-  static constexpr BaseType getMid() {
-return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
-  }
-
-  static constexpr bool isSigned() { return std::is_signed::value; }
-  static constexpr BaseType fromInt(int X) { return static_cast(X); }
-
-  static llvm::APSInt Base;
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * CHAR_BIT,
+ std::is_unsigned::value};
+Base = X;
+return BVF.getValue(Base);
   }
 
   Range from(const RawRange &Init) {
@@ -160,7 +169,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +177,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -183,29 +215,19 @@
 
 } // namespace
 
-template 
-llvm::APSInt RangeSetTest::Base{sizeof(BaseType) * 8, !isSigned()};
-
 using IntTypes = ::testing::Types;
 TYPED_TEST_SUITE(RangeSetTest, IntTypes, );
 
 TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
-  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
-
-  constexpr TypeParam MIN = TestFixture::getMin();
-  constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 TypeParam MID = TestFixture::getMid();
-  constexpr TypeParam A = MID - TestFixture::fromInt(42 

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 393509.
ASDenysPetrov added a comment.

Fixed code formatting in the unit test file according to remarks. Ready to load.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -35,12 +35,34 @@
   const RangeSet &Set) {
   return OS << toString(Set);
 }
+// We need it here for better fail diagnostics from gtest.
+LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS,
+  const Range &R) {
+  return OS << toString(R);
+}
 
 } // namespace ento
 } // namespace clang
 
 namespace {
 
+template  struct TestValues {
+  static constexpr T MIN = std::numeric_limits::min();
+  static constexpr T MAX = std::numeric_limits::max();
+  // 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).
+  static constexpr T MID =
+  std::is_signed::value ? 0 : ~(static_cast(-1) / static_cast(2));
+  static constexpr T A = MID - (MAX - MID) / 3 * 2;
+  static constexpr T B = MID - (MAX - MID) / 3;
+  static constexpr T C = -B;
+  static constexpr T D = -A;
+
+  static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+"Values shall be in an ascending order");
+};
+
 template  class RangeSetTest : public testing::Test {
 public:
   // Init block
@@ -55,24 +77,11 @@
   using RawRange = std::pair;
   using RawRangeSet = std::initializer_list;
 
-  static constexpr BaseType getMin() {
-return std::numeric_limits::min();
-  }
-  static constexpr BaseType getMax() {
-return std::numeric_limits::max();
-  }
-  static constexpr BaseType getMid() {
-return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
-  }
-
-  static constexpr bool isSigned() { return std::is_signed::value; }
-  static constexpr BaseType fromInt(int X) { return static_cast(X); }
-
-  static llvm::APSInt Base;
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * CHAR_BIT,
+ std::is_unsigned::value};
+Base = X;
+return BVF.getValue(Base);
   }
 
   Range from(const RawRange &Init) {
@@ -160,7 +169,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +177,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -183,29 +215,19 @@
 
 } // namespace
 
-template 
-llvm::APSInt RangeSetTest::Base{sizeof(BaseType) * 8, !isSigned()};
-
 using IntTypes = ::testing::Types;
 TYPED_TEST_SUITE(RangeSetTest, IntTypes, );
 
 TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
-  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
-
-  constexpr TypeParam MIN = TestFixture::getMin();
-  constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 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,
- 

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added a comment.

@martong

> Nice, assiduous work!

Many thanks for your time! Your work is not less assiduous!

> (LHS, RHS) swaps

it doesn't really matter, as the operation is comutative, but, yes, it does 
matter to depict the particular test case. I'll revise twise LHS-RHS's.

> I am going to continue with the next patch in the stack. I recognize that the 
> handling of casts is very important and problems related to not handling them 
> occurs even more frequently as other parts of the engine evolve (e.g. 
> https://reviews.llvm.org/D113753#3167134)

Aha. I saw you patch. I'll join to review it.




Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:441
+  //___/__/_\__\___   ___/___\___
+  this->checkUnite({{MID, MID}}, {A, D}, {{A, D}});
+  this->checkUnite({{B, C}}, {A, D}, {{A, D}});

martong wrote:
> 
There are three overloads of `checkUnite` which correspond to three overloads 
of `RangeSet::unite`. I made it consistent to other check-functions (`add` 
e.g.).



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:449
+  //___/___\___   ___/___\___
+  this->checkUnite({{MIN, MIN}}, MIN, {{MIN, MIN}});
+  this->checkUnite({{A, B}}, {A, B}, {{A, B}});

martong wrote:
> I think, either we should use `{{X, X}}` or `X` everywhere, but not mixed. 
This tests different oveloaded versions of `RangeSet::unite`.



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:528-529
+  //_/__\_/__\_/\_/\_/\_   _/__\_/__\_/\_/\_/\_
+  this->checkUnite({{MIN, A}, {A + 2, B}}, {{MID, C}, {C + 2, D - 2}, {D, 
MAX}},
+   {{MIN, A}, {A + 2, B}, {MID, C}, {C + 2, D - 2}, {D, MAX}});
+  this->checkUnite({{MIN, MIN}, {A, A}}, {{B, B}, {C, C}, {MAX, MAX}},

martong wrote:
> I think we could better format these more complex cases.
clang-fromat acts on its own. But I agree, it looks the way better. I'll 
consider wrapping it into `// clang-format on/off` directives.



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:590-592
+  this->checkUnite({{A, B - 1}, {B + 1, C - 1}, {C + 2, D}, {MAX - 1, MAX}},
+   {{MIN, MIN}, {B, MID}, {MID + 1, C}, {C + 4, D - 1}},
+   {{MIN, MIN}, {A, C}, {C + 2, D}, {MAX - 1, MAX}});

martong wrote:
> martong wrote:
> > 
> What do you think about this format? The result can be easily verified this 
> way I think, but a bit ugly ...
I think ASCII art does this job. Let code look as code :)


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Gabor Marton via Phabricator via cfe-commits]

martong accepted this revision.
martong added a comment.

Nice, assiduous work! The tests are awesome!
LGTM, with minor revisions. Please check out my suggestions about the tests' 
formatting and there are those disturbing (LHS, RHS) swaps in the comments.

I am going to continue with the next patch in the stack. I recognize that the 
handling of casts is very important and problems related to not handling them 
occurs even more frequently as other parts of the engine evolve (e.g. 
https://reviews.llvm.org/D113753#3167134)




Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:441
+  //___/__/_\__\___   ___/___\___
+  this->checkUnite({{MID, MID}}, {A, D}, {{A, D}});
+  this->checkUnite({{B, C}}, {A, D}, {{A, D}});





Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:449
+  //___/___\___   ___/___\___
+  this->checkUnite({{MIN, MIN}}, MIN, {{MIN, MIN}});
+  this->checkUnite({{A, B}}, {A, B}, {{A, B}});

I think, either we should use `{{X, X}}` or `X` everywhere, but not mixed. 



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:525-526
+
+  // RHS =>
+  // LHS =>   /\   /\=   __   __
+  //_/__\_/__\_/\_/\_/\_   _/__\_/__\_/\_/\_/\_

LHS and RHS is swapped here?



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:528-529
+  //_/__\_/__\_/\_/\_/\_   _/__\_/__\_/\_/\_/\_
+  this->checkUnite({{MIN, A}, {A + 2, B}}, {{MID, C}, {C + 2, D - 2}, {D, 
MAX}},
+   {{MIN, A}, {A + 2, B}, {MID, C}, {C + 2, D - 2}, {D, MAX}});
+  this->checkUnite({{MIN, MIN}, {A, A}}, {{B, B}, {C, C}, {MAX, MAX}},

I think we could better format these more complex cases.



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:533-534
+
+  // RHS =>
+  // LHS => /\   /\   =__   __
+  //_/\_/\_/\__/__\_/__\_   _/\_/\_/\_/__\_/__\_

LHS and RHS is swapped?



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:536-537
+  //_/\_/\_/\__/__\_/__\_   _/\_/\_/\_/__\_/__\_
+  this->checkUnite({{C + 2, D - 2}, {D, MAX}}, {{MIN, A}, {A + 2, B}, {MID, 
C}},
+   {{MIN, A}, {A + 2, B}, {MID, C}, {C + 2, D - 2}, {D, MAX}});
+  this->checkUnite({{C, C}, {MAX, MAX}}, {{MIN, MIN}, {A, A}, {B, B}},





Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:541-542
+
+  // RHS =>
+  // LHS =>   _   /\   _   /\   _   /\  =
+  //_/_\_/__\_/_\_/__\_/_\_/__\_

LHS and RHS is swapped?



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:558-559
+
+  // RHS =>
+  // LHS =>   /\   _   /\   _   /\   _  =
+  //_/__\_/_\_/__\_/_\_/__\_/_\_

LHS and RHS is swapped here as well.



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:582
+  this->checkUnite({{A, A}, {B, MID}, {D, D}},
+   {{A, A}, {B, B}, {MID + 1, D - 1}}, {{A, A}, {B, D}});
+





Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:590-592
+  this->checkUnite({{A, B - 1}, {B + 1, C - 1}, {C + 2, D}, {MAX - 1, MAX}},
+   {{MIN, MIN}, {B, MID}, {MID + 1, C}, {C + 4, D - 1}},
+   {{MIN, MIN}, {A, C}, {C + 2, D}, {MAX - 1, MAX}});





Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:590-592
+  this->checkUnite({{A, B - 1}, {B + 1, C - 1}, {C + 2, D}, {MAX - 1, MAX}},
+   {{MIN, MIN}, {B, MID}, {MID + 1, C}, {C + 4, D - 1}},
+   {{MIN, MIN}, {A, C}, {C + 2, D}, {MAX - 1, MAX}});

martong wrote:
> 
What do you think about this format? The result can be easily verified this way 
I think, but a bit ugly ...


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Gabor Marton via Phabricator via cfe-commits]

martong added a comment.

Thanks for the update, I am okay with the `.cpp` file, now I continue the 
review with the tests.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 388219.
ASDenysPetrov added a comment.

Fixed comments.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -35,12 +35,34 @@
   const RangeSet &Set) {
   return OS << toString(Set);
 }
+// We need it here for better fail diagnostics from gtest.
+LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS,
+  const Range &R) {
+  return OS << toString(R);
+}
 
 } // namespace ento
 } // namespace clang
 
 namespace {
 
+template  struct TestValues {
+  static constexpr T MIN = std::numeric_limits::min();
+  static constexpr T MAX = std::numeric_limits::max();
+  // 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).
+  static constexpr T MID =
+  std::is_signed::value ? 0 : ~(static_cast(-1) / static_cast(2));
+  static constexpr T A = MID - (MAX - MID) / 3 * 2;
+  static constexpr T B = MID - (MAX - MID) / 3;
+  static constexpr T C = -B;
+  static constexpr T D = -A;
+
+  static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+"Values shall be in an ascending order");
+};
+
 template  class RangeSetTest : public testing::Test {
 public:
   // Init block
@@ -55,24 +77,11 @@
   using RawRange = std::pair;
   using RawRangeSet = std::initializer_list;
 
-  static constexpr BaseType getMin() {
-return std::numeric_limits::min();
-  }
-  static constexpr BaseType getMax() {
-return std::numeric_limits::max();
-  }
-  static constexpr BaseType getMid() {
-return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
-  }
-
-  static constexpr bool isSigned() { return std::is_signed::value; }
-  static constexpr BaseType fromInt(int X) { return static_cast(X); }
-
-  static llvm::APSInt Base;
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * CHAR_BIT,
+ std::is_unsigned::value};
+Base = X;
+return BVF.getValue(Base);
   }
 
   Range from(const RawRange &Init) {
@@ -160,7 +169,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +177,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -183,29 +215,19 @@
 
 } // namespace
 
-template 
-llvm::APSInt RangeSetTest::Base{sizeof(BaseType) * 8, !isSigned()};
-
 using IntTypes = ::testing::Types;
 TYPED_TEST_SUITE(RangeSetTest, IntTypes, );
 
 TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
-  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
-
-  constexpr TypeParam MIN = TestFixture::getMin();
-  constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 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");
+  using TV = Te

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added inline comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:229-233
+// We want to keep the following invariant at all times:
+// ---[ First -->
+// -[ Second --->
+if (First->From() > Second->From())
+  swapIterators(First, FirstEnd, Second, SecondEnd);

martong wrote:
> I am not sure about this, but perhaps we could put this `swapIterators` call 
> right at the beginning of the nested `while` loop (L243). That would 
> eliminate the need to call it again at the end of the second while loop.
I'm afraid, it is not the case. Every loop needs its own `swapIterators`. As 
you can see, `swapIterators` in the nested loop invokes not always because of 
`break;` in the middle. Otherwise, it would invokes each time. But I checked 
your suggestion. It doesn't work.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:243
+// Loop where the invariant holds.
+while (true) {
+  // Skip all enclosed ranges.

martong wrote:
> So, this loop is about to merge conjunct Ranges. The first time when we find 
> disjoint Ranges then we break out. (Or we return once we reach the end of any 
> of the RangeSets.)
> This makes we wonder, if it would be possible to split this `while` loop into 
> a lambda named `mergeConjunctRanges` ?
I'm not in favor of introducing another level of abstraction. It would divide 
the flow/comments and could reduce readability and performance which is crucial 
here.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Gabor Marton via Phabricator via cfe-commits]

martong added a comment.

Gentle ping.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Gabor Marton via Phabricator via cfe-commits]

martong added a comment.

Thanks Denys for the update! Very good! However, I think maybe we could make 
the code a bit more simpler.




Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:229-233
+// We want to keep the following invariant at all times:
+// ---[ First -->
+// -[ Second --->
+if (First->From() > Second->From())
+  swapIterators(First, FirstEnd, Second, SecondEnd);

I am not sure about this, but perhaps we could put this `swapIterators` call 
right at the beginning of the nested `while` loop (L243). That would eliminate 
the need to call it again at the end of the second while loop.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:243
+// Loop where the invariant holds.
+while (true) {
+  // Skip all enclosed ranges.

So, this loop is about to merge conjunct Ranges. The first time when we find 
disjoint Ranges then we break out. (Or we return once we reach the end of any 
of the RangeSets.)
This makes we wonder, if it would be possible to split this `while` loop into a 
lambda named `mergeConjunctRanges` ?



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:290-292
+  // case 1: --[ First ]-[ First + 1 ]-->
+  // case 2: --[ First]-[ First + 1 ]--->
+  // ---[ Second + 1]--->

Should this be like in the code suggestion? You incremented `First` at L276.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:293
+  // ---[ Second + 1]--->
+  // In any case First + 1 goes after Second.
+  // Make sure that the loop invariant holds.

?


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added inline comments.



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:81
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * 8,
+ std::is_unsigned::value};

ASDenysPetrov wrote:
> steakhal wrote:
> > ASDenysPetrov wrote:
> > > steakhal wrote:
> > > > ASDenysPetrov wrote:
> > > > > steakhal wrote:
> > > > > > Shouldn't you use `sizeof(BaseType) * CHAR_BIT` instead?
> > > > > Agree. It's better to avoid magic numbers. I'll fix.
> > > > It's not only that but just imagine testing a clang on a special 
> > > > hardware where they have let's say 9 bit bytes, for parity or something 
> > > > similar stuff.
> > > > The test would suddenly break.
> > > > Although I suspect there would be many more things to break TBH xD
> > > I am always skeptical about using`CHAR_BIT`, beacuse it represents bit 
> > > number in `char`. And what if it would be 16 for instance (aka 2 bytes). 
> > > But my intention is to get an amount of bits for a particular type. And I 
> > > want something to represent a number of bits in a byte as a fundamental 
> > > unit, but not something that depends on a `char` size on a particular 
> > > platform.
> > > I would better introduce something like `constexpr size_t BITS_IN_BYTE = 
> > > 8;`.
> > [[ https://eel.is/c++draft/basic.memobj#footnote-22 | basic.memobj 6.7.1/22 
> > ]]:
> > >The number of bits in a byte is reported by the macro `CHAR_­BIT` in the 
> > >header ``.
> These legacy names... :) I'll update.
BTW, the first time this definition appeared only in C++17 in a footnote. The 
committee is not yet confident enough about CHAR_BIT that it still resides 
there :)


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 383065.
ASDenysPetrov added a comment.

Fixed nits.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -35,12 +35,34 @@
   const RangeSet &Set) {
   return OS << toString(Set);
 }
+// We need it here for better fail diagnostics from gtest.
+LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS,
+  const Range &R) {
+  return OS << toString(R);
+}
 
 } // namespace ento
 } // namespace clang
 
 namespace {
 
+template  struct TestValues {
+  static constexpr T MIN = std::numeric_limits::min();
+  static constexpr T MAX = std::numeric_limits::max();
+  // 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).
+  static constexpr T MID =
+  std::is_signed::value ? 0 : ~(static_cast(-1) / static_cast(2));
+  static constexpr T A = MID - (MAX - MID) / 3 * 2;
+  static constexpr T B = MID - (MAX - MID) / 3;
+  static constexpr T C = -B;
+  static constexpr T D = -A;
+
+  static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+"Values shall be in an ascending order");
+};
+
 template  class RangeSetTest : public testing::Test {
 public:
   // Init block
@@ -55,24 +77,11 @@
   using RawRange = std::pair;
   using RawRangeSet = std::initializer_list;
 
-  static constexpr BaseType getMin() {
-return std::numeric_limits::min();
-  }
-  static constexpr BaseType getMax() {
-return std::numeric_limits::max();
-  }
-  static constexpr BaseType getMid() {
-return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
-  }
-
-  static constexpr bool isSigned() { return std::is_signed::value; }
-  static constexpr BaseType fromInt(int X) { return static_cast(X); }
-
-  static llvm::APSInt Base;
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * CHAR_BIT,
+ std::is_unsigned::value};
+Base = X;
+return BVF.getValue(Base);
   }
 
   Range from(const RawRange &Init) {
@@ -160,7 +169,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +177,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -183,29 +215,19 @@
 
 } // namespace
 
-template 
-llvm::APSInt RangeSetTest::Base{sizeof(BaseType) * 8, !isSigned()};
-
 using IntTypes = ::testing::Types;
 TYPED_TEST_SUITE(RangeSetTest, IntTypes, );
 
 TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
-  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
-
-  constexpr TypeParam MIN = TestFixture::getMin();
-  constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 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");
+  using TV = TestVa

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added inline comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:200-204
+} else {
+  //[ First ]-->
+  //[ Second  ]--->
+  // MIN^
+  // The First range is entirely inside the Second one.

steakhal wrote:
> Might be `First->To() == Second->To()`. In this case the comment is not 
> completely accurate.
I'll update.



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:81
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * 8,
+ std::is_unsigned::value};

steakhal wrote:
> ASDenysPetrov wrote:
> > steakhal wrote:
> > > ASDenysPetrov wrote:
> > > > steakhal wrote:
> > > > > Shouldn't you use `sizeof(BaseType) * CHAR_BIT` instead?
> > > > Agree. It's better to avoid magic numbers. I'll fix.
> > > It's not only that but just imagine testing a clang on a special hardware 
> > > where they have let's say 9 bit bytes, for parity or something similar 
> > > stuff.
> > > The test would suddenly break.
> > > Although I suspect there would be many more things to break TBH xD
> > I am always skeptical about using`CHAR_BIT`, beacuse it represents bit 
> > number in `char`. And what if it would be 16 for instance (aka 2 bytes). 
> > But my intention is to get an amount of bits for a particular type. And I 
> > want something to represent a number of bits in a byte as a fundamental 
> > unit, but not something that depends on a `char` size on a particular 
> > platform.
> > I would better introduce something like `constexpr size_t BITS_IN_BYTE = 
> > 8;`.
> [[ https://eel.is/c++draft/basic.memobj#footnote-22 | basic.memobj 6.7.1/22 
> ]]:
> >The number of bits in a byte is reported by the macro `CHAR_­BIT` in the 
> >header ``.
These legacy names... :) I'll update.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Balázs Benics via Phabricator via cfe-commits]

steakhal added inline comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:200-204
+} else {
+  //[ First ]-->
+  //[ Second  ]--->
+  // MIN^
+  // The First range is entirely inside the Second one.

Might be `First->To() == Second->To()`. In this case the comment is not 
completely accurate.



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:81
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * 8,
+ std::is_unsigned::value};

ASDenysPetrov wrote:
> steakhal wrote:
> > ASDenysPetrov wrote:
> > > steakhal wrote:
> > > > Shouldn't you use `sizeof(BaseType) * CHAR_BIT` instead?
> > > Agree. It's better to avoid magic numbers. I'll fix.
> > It's not only that but just imagine testing a clang on a special hardware 
> > where they have let's say 9 bit bytes, for parity or something similar 
> > stuff.
> > The test would suddenly break.
> > Although I suspect there would be many more things to break TBH xD
> I am always skeptical about using`CHAR_BIT`, beacuse it represents bit number 
> in `char`. And what if it would be 16 for instance (aka 2 bytes). But my 
> intention is to get an amount of bits for a particular type. And I want 
> something to represent a number of bits in a byte as a fundamental unit, but 
> not something that depends on a `char` size on a particular platform.
> I would better introduce something like `constexpr size_t BITS_IN_BYTE = 8;`.
[[ https://eel.is/c++draft/basic.memobj#footnote-22 | basic.memobj 6.7.1/22 ]]:
>The number of bits in a byte is reported by the macro `CHAR_­BIT` in the 
>header ``.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 382679.
ASDenysPetrov added a comment.

@martong @steakhal 
Updated according to your comments. Thank you!


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -35,12 +35,34 @@
   const RangeSet &Set) {
   return OS << toString(Set);
 }
+// We need it here for better fail diagnostics from gtest.
+LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS,
+  const Range &R) {
+  return OS << toString(R);
+}
 
 } // namespace ento
 } // namespace clang
 
 namespace {
 
+template  struct TestValues {
+  static constexpr T MIN = std::numeric_limits::min();
+  static constexpr T MAX = std::numeric_limits::max();
+  // 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).
+  static constexpr T MID =
+  std::is_signed::value ? 0 : ~(static_cast(-1) / static_cast(2));
+  static constexpr T A = MID - (MAX - MID) / 3 * 2;
+  static constexpr T B = MID - (MAX - MID) / 3;
+  static constexpr T C = -B;
+  static constexpr T D = -A;
+
+  static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+"Values shall be in an ascending order");
+};
+
 template  class RangeSetTest : public testing::Test {
 public:
   // Init block
@@ -54,25 +76,13 @@
   using Self = RangeSetTest;
   using RawRange = std::pair;
   using RawRangeSet = std::initializer_list;
+  static constexpr size_t BITS_IN_BYTE = 8;
 
-  static constexpr BaseType getMin() {
-return std::numeric_limits::min();
-  }
-  static constexpr BaseType getMax() {
-return std::numeric_limits::max();
-  }
-  static constexpr BaseType getMid() {
-return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
-  }
-
-  static constexpr bool isSigned() { return std::is_signed::value; }
-  static constexpr BaseType fromInt(int X) { return static_cast(X); }
-
-  static llvm::APSInt Base;
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * BITS_IN_BYTE,
+ std::is_unsigned::value};
+Base = X;
+return BVF.getValue(Base);
   }
 
   Range from(const RawRange &Init) {
@@ -160,7 +170,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +178,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -183,29 +216,19 @@
 
 } // namespace
 
-template 
-llvm::APSInt RangeSetTest::Base{sizeof(BaseType) * 8, !isSigned()};
-
 using IntTypes = ::testing::Types;
 TYPED_TEST_SUITE(RangeSetTest, IntTypes, );
 
 TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
-  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
-
-  constexpr TypeParam MIN = TestFixture::getMin();
-  constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 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 <

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added a comment.

@martong 
Thanks for your inlines. I'll update the patch.




Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:81
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * 8,
+ std::is_unsigned::value};

steakhal wrote:
> ASDenysPetrov wrote:
> > steakhal wrote:
> > > Shouldn't you use `sizeof(BaseType) * CHAR_BIT` instead?
> > Agree. It's better to avoid magic numbers. I'll fix.
> It's not only that but just imagine testing a clang on a special hardware 
> where they have let's say 9 bit bytes, for parity or something similar stuff.
> The test would suddenly break.
> Although I suspect there would be many more things to break TBH xD
I am always skeptical about using`CHAR_BIT`, beacuse it represents bit number 
in `char`. And what if it would be 16 for instance (aka 2 bytes). But my 
intention is to get an amount of bits for a particular type. And I want 
something to represent a number of bits in a byte as a fundamental unit, but 
not something that depends on a `char` size on a particular platform.
I would better introduce something like `constexpr size_t BITS_IN_BYTE = 8;`.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Gabor Marton via Phabricator via cfe-commits]

martong added a comment.

I think, the visual comments that we have in `intersect` makes the code of 
`intersect` a lot easier to follow. Could you please add similar visual 
comments here? Also, I find `First` and `Second` in `intersect` way more better 
naming than `I1` and `I2`, could you please update?




Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:169
+
+  iterator I1 = LHS.begin();
+  iterator E1 = LHS.end();

I think, the naming conventions we have in `intersect` are easier to follow. 
Could we call `I1` as `First` and `I2` as `Second`?



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:181
+  // Append the rest of the ranges from another range set to the Result
+  // and return the later.
+  auto AppendRest = [&Result](iterator I, iterator E) {





Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:188
+  // Handle a corner case first when both range sets start from MIN.
+  // This helps to avoid complicated conditions below.
+  if (Min == I1->From() && Min == I2->From()) {

It is not clear what is the complicated condition that you'd like to avoid. 
Could you please elaborate?



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:189-201
+  if (Min == I1->From() && Min == I2->From()) {
+if (I1->To() > I2->To()) {
+  // The second range is entirely inside the first one. Skip it.
+  // Check for the end of the range for every incrementation.
+  if (++I2 == E2)
+return AppendRest(I1, E1);
+} else {

I'd like to see similar visual comments that we have in `intersect`.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:204-205
+  while (true) {
+// I1->From() shall be lower than I2->From().
+// Otherwise, swap the iterators.
+if (I1->From() > I2->From()) {

Let's reuse as much as possible from `intersect`, both code and comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:207-208
+if (I1->From() > I2->From()) {
+  std::swap(I1, I2);
+  std::swap(E1, E2);
+}

We could reuse `SwapIterators` from `intersect`. Of course for that we need to 
make a real function out of the lambda.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:211
+
+// At this point, the next range surely starts with I1->From().
+F = &I1->From();





Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:212
+// At this point, the next range surely starts with I1->From().
+F = &I1->From();
+

Let's be consistent with `intersect`. Also, you could introduce the variable 
here, and it is not needed to declare that at L176.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:214
+
+// Build a new range.
+while (true) {





Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:242
+  // Every next range of the first set always go after the second range.
+  // So swap the iterators without any check.
+  std::swap(I1, I2);




CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Balázs Benics via Phabricator via cfe-commits]

steakhal added inline comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:149
+
+RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt Point) {
+  return unite(Original, Range(ValueFactory.getValue(Point)));

martong wrote:
> ASDenysPetrov wrote:
> > steakhal wrote:
> > > Why do you take `APSInt`s by value? Generally, we take them by reference.
> > I want to send a message to the caller that he can pass an arbitrary 
> > **APSInt** without warrying about making it permanent (aka stored by the 
> > Factory). But we can revise this contract and carry this responsibility to 
> > a caller.
> > Why do you take `APSInt`s by value? Generally, we take them by reference.
> 
> Actually, it is specific to `BasicValueFactory` to cache the `APSInt`s, 
> however, it might not be the best practice. I doubt that somebody has ever 
> measured the performance of passing APSInts by value, so my guess is the 
> caching of `APSInt`s might be an early optimization that might be more 
> harmful than advantageous. On top of all this, we do the caching 
> inconsistently, just consider the member functions of `APSIntType`, they all 
> return by value.
> 
> Perhaps (totally independently from this patch of course), it might be worth 
> to have a measurement/comparison with removed cache and pass by value.
> 
Okay, then we shall leave this as-is now.



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:81
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * 8,
+ std::is_unsigned::value};

ASDenysPetrov wrote:
> steakhal wrote:
> > Shouldn't you use `sizeof(BaseType) * CHAR_BIT` instead?
> Agree. It's better to avoid magic numbers. I'll fix.
It's not only that but just imagine testing a clang on a special hardware where 
they have let's say 9 bit bytes, for parity or something similar stuff.
The test would suddenly break.
Although I suspect there would be many more things to break TBH xD


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Gabor Marton via Phabricator via cfe-commits]

martong added inline comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:149
+
+RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt Point) {
+  return unite(Original, Range(ValueFactory.getValue(Point)));

ASDenysPetrov wrote:
> steakhal wrote:
> > Why do you take `APSInt`s by value? Generally, we take them by reference.
> I want to send a message to the caller that he can pass an arbitrary 
> **APSInt** without warrying about making it permanent (aka stored by the 
> Factory). But we can revise this contract and carry this responsibility to a 
> caller.
> Why do you take `APSInt`s by value? Generally, we take them by reference.

Actually, it is specific to `BasicValueFactory` to cache the `APSInt`s, 
however, it might not be the best practice. I doubt that somebody has ever 
measured the performance of passing APSInts by value, so my guess is the 
caching of `APSInt`s might be an early optimization that might be more harmful 
than advantageous. On top of all this, we do the caching inconsistently, just 
consider the member functions of `APSIntType`, they all return by value.

Perhaps (totally independently from this patch of course), it might be worth to 
have a measurement/comparison with removed cache and pass by value.



CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added a comment.

In D99797#3059203 , @steakhal wrote:

> PS: the test coverage is outstanding!

Thank you for this analysis.




Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:149
+
+RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt Point) {
+  return unite(Original, Range(ValueFactory.getValue(Point)));

steakhal wrote:
> Why do you take `APSInt`s by value? Generally, we take them by reference.
I want to send a message to the caller that he can pass an arbitrary **APSInt** 
without warrying about making it permanent (aka stored by the Factory). But we 
can revise this contract and carry this responsibility to a caller.



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:81
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * 8,
+ std::is_unsigned::value};

steakhal wrote:
> Shouldn't you use `sizeof(BaseType) * CHAR_BIT` instead?
Agree. It's better to avoid magic numbers. I'll fix.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Balázs Benics via Phabricator via cfe-commits]

steakhal added a comment.

I still need to chew through the code but on a high level, I think it looks 
correct.
PS: the test coverage is outstanding! F19575968: unite-patch-line-coverage.zip 





Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:149
+
+RangeSet RangeSet::Factory::unite(RangeSet Original, llvm::APSInt Point) {
+  return unite(Original, Range(ValueFactory.getValue(Point)));

Why do you take `APSInt`s by value? Generally, we take them by reference.



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:81
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * 8,
+ std::is_unsigned::value};

Shouldn't you use `sizeof(BaseType) * CHAR_BIT` instead?


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Gabor Marton via Phabricator via cfe-commits]

martong added a comment.

@ASDenysPetrov Nice work! I really appreciate the hard work you guys (with 
@vsavchenko) had done here. I really like that you have created visible test 
cases (though the last ones are a bit cryptic for me). It is going to take some 
more time to finish my review.




Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:179
+
+  // This calls when there are no ranges left in one of the ranges.
+  // Append the rest of the ranges from another range set to the Result

`This is called`


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added a comment.

Gentle ping.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 374265.
ASDenysPetrov added a comment.

Rebased. Review, please.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -35,12 +35,34 @@
   const RangeSet &Set) {
   return OS << toString(Set);
 }
+// We need it here for better fail diagnostics from gtest.
+LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS,
+  const Range &R) {
+  return OS << toString(R);
+}
 
 } // namespace ento
 } // namespace clang
 
 namespace {
 
+template  struct TestValues {
+  static constexpr T MIN = std::numeric_limits::min();
+  static constexpr T MAX = std::numeric_limits::max();
+  // 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).
+  static constexpr T MID =
+  std::is_signed::value ? 0 : ~(static_cast(-1) / static_cast(2));
+  static constexpr T A = MID - (MAX - MID) / 3 * 2;
+  static constexpr T B = MID - (MAX - MID) / 3;
+  static constexpr T C = -B;
+  static constexpr T D = -A;
+
+  static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+"Values shall be in an ascending order");
+};
+
 template  class RangeSetTest : public testing::Test {
 public:
   // Init block
@@ -55,24 +77,11 @@
   using RawRange = std::pair;
   using RawRangeSet = std::initializer_list;
 
-  static constexpr BaseType getMin() {
-return std::numeric_limits::min();
-  }
-  static constexpr BaseType getMax() {
-return std::numeric_limits::max();
-  }
-  static constexpr BaseType getMid() {
-return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
-  }
-
-  static constexpr bool isSigned() { return std::is_signed::value; }
-  static constexpr BaseType fromInt(int X) { return static_cast(X); }
-
-  static llvm::APSInt Base;
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * 8,
+ std::is_unsigned::value};
+Base = X;
+return BVF.getValue(Base);
   }
 
   Range from(const RawRange &Init) {
@@ -160,7 +169,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +177,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -183,29 +215,19 @@
 
 } // namespace
 
-template 
-llvm::APSInt RangeSetTest::Base{sizeof(BaseType) * 8, !isSigned()};
-
 using IntTypes = ::testing::Types;
 TYPED_TEST_SUITE(RangeSetTest, IntTypes, );
 
 TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
-  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
-
-  constexpr TypeParam MIN = TestFixture::getMin();
-  constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 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");
+  using TV = 

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added a comment.

How about this patch and the entire stack?


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 358656.
ASDenysPetrov added a comment.

Rebased


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -35,12 +35,34 @@
   const RangeSet &Set) {
   return OS << toString(Set);
 }
+// We need it here for better fail diagnostics from gtest.
+LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS,
+  const Range &R) {
+  return OS << toString(R);
+}
 
 } // namespace ento
 } // namespace clang
 
 namespace {
 
+template  struct TestValues {
+  static constexpr T MIN = std::numeric_limits::min();
+  static constexpr T MAX = std::numeric_limits::max();
+  // 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).
+  static constexpr T MID =
+  std::is_signed::value ? 0 : ~(static_cast(-1) / static_cast(2));
+  static constexpr T A = MID - (MAX - MID) / 3 * 2;
+  static constexpr T B = MID - (MAX - MID) / 3;
+  static constexpr T C = -B;
+  static constexpr T D = -A;
+
+  static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+"Values shall be in an ascending order");
+};
+
 template  class RangeSetTest : public testing::Test {
 public:
   // Init block
@@ -55,24 +77,11 @@
   using RawRange = std::pair;
   using RawRangeSet = std::initializer_list;
 
-  static constexpr BaseType getMin() {
-return std::numeric_limits::min();
-  }
-  static constexpr BaseType getMax() {
-return std::numeric_limits::max();
-  }
-  static constexpr BaseType getMid() {
-return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
-  }
-
-  static constexpr bool isSigned() { return std::is_signed::value; }
-  static constexpr BaseType fromInt(int X) { return static_cast(X); }
-
-  static llvm::APSInt Base;
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * 8,
+ std::is_unsigned::value};
+Base = X;
+return BVF.getValue(Base);
   }
 
   Range from(const RawRange &Init) {
@@ -160,7 +169,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +177,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -183,29 +215,19 @@
 
 } // namespace
 
-template 
-llvm::APSInt RangeSetTest::Base{sizeof(BaseType) * 8, !isSigned()};
-
 using IntTypes = ::testing::Types;
 TYPED_TEST_SUITE(RangeSetTest, IntTypes, );
 
 TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
-  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
-
-  constexpr TypeParam MIN = TestFixture::getMin();
-  constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 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");
+  using TV = TestValues;
+  co

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 352851.
ASDenysPetrov added a comment.

Updated. Removed `F` as flag. Replaced `goto` with closure. Detailed comments 
and fixed typos.

@vsavchenko made changes according your suggestions.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -35,12 +35,34 @@
   const RangeSet &Set) {
   return OS << toString(Set);
 }
+// We need it here for better fail diagnostics from gtest.
+LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS,
+  const Range &R) {
+  return OS << toString(R);
+}
 
 } // namespace ento
 } // namespace clang
 
 namespace {
 
+template  struct TestValues {
+  static constexpr T MIN = std::numeric_limits::min();
+  static constexpr T MAX = std::numeric_limits::max();
+  // 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).
+  static constexpr T MID =
+  std::is_signed::value ? 0 : ~(static_cast(-1) / static_cast(2));
+  static constexpr T A = MID - (MAX - MID) / 3 * 2;
+  static constexpr T B = MID - (MAX - MID) / 3;
+  static constexpr T C = -B;
+  static constexpr T D = -A;
+
+  static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+"Values shall be in an ascending order");
+};
+
 template  class RangeSetTest : public testing::Test {
 public:
   // Init block
@@ -55,24 +77,11 @@
   using RawRange = std::pair;
   using RawRangeSet = std::initializer_list;
 
-  static constexpr BaseType getMin() {
-return std::numeric_limits::min();
-  }
-  static constexpr BaseType getMax() {
-return std::numeric_limits::max();
-  }
-  static constexpr BaseType getMid() {
-return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
-  }
-
-  static constexpr bool isSigned() { return std::is_signed::value; }
-  static constexpr BaseType fromInt(int X) { return static_cast(X); }
-
-  static llvm::APSInt Base;
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * 8,
+ std::is_unsigned::value};
+Base = X;
+return BVF.getValue(Base);
   }
 
   Range from(const RawRange &Init) {
@@ -160,7 +169,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +177,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -183,29 +215,19 @@
 
 } // namespace
 
-template 
-llvm::APSInt RangeSetTest::Base{sizeof(BaseType) * 8, !isSigned()};
-
 using IntTypes = ::testing::Types;
 TYPED_TEST_SUITE(RangeSetTest, IntTypes, );
 
 TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
-  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
-
-  constexpr TypeParam MIN = TestFixture::getMin();
-  constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 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 

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Valeriy Savchenko via Phabricator via cfe-commits]

vsavchenko added a comment.

I think this iteration is much better, it requires way more description as it 
has now.  You didn't actually describe anywhere how this algorithm actually 
works.




Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:200-201
+}
+
+// Build a new range.
+while (true) {

At this point, we know for a fact that the next range we are going to add to 
our result set starts with `I1->From()`.  No need to check `F` for null or 
anything



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:210
+
+  // Check if the second range intersects or adjucent to the first one.
+  if (I1->To() < I2->From() - One)

nit: "**is** adj**a**cent"



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:212
+  if (I1->To() < I2->From() - One)
+break;
+

Why `break`?  At this point we know that what we peaked into is actually a part 
of another range (in terms of the end result).
And this range is over, you just need to add it to the final result!



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:214-218
+  // We use `F` as a flag to notify that we are in a building of a new
+  // range. Set `From` of a new range if it is not set yet. If it has
+  // already been set, then we are inside this range and just looking for
+  // its end.
+  if (!F)

You actually don't need it, the moment you swap two iterators and find out that 
`I1->From() <= I2->From()`, that's it `I1->From()` is the beginning of the new 
range.  No need to carry extra flag here.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:227
+  // Now we can surely swap the iterators without any check, as we know
+  // I2-From() to be lower than I1-From().
+  std::swap(I1, I2);

 nit
Additionally, you didn't tell your readers WHY you are even swapping iterators 
in the first place and what relationship they have.  You need to communicate in 
terms of invariants.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:244
+if (++I1 == E1)
+  goto end1;
+  };

This goto is always finishing with a return, so we can refactor `goto end1` 
into something like `return copyIntoResult(I1, E1);` and `goto end2` into 
`return copyIntoResult(I2, E2);`.
As I mentioned before, optional `F` should be removed.  On every path we should 
know deterministically what is the beginning and what is the end of the range 
that we are trying to add.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 348294.
ASDenysPetrov added a comment.

Fixed the issue. Added more unit tests.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -41,6 +41,23 @@
 
 namespace {
 
+template  struct TestValues {
+  static constexpr T MIN = std::numeric_limits::min();
+  static constexpr T MAX = std::numeric_limits::max();
+  // 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).
+  static constexpr T MID =
+  std::is_signed::value ? 0 : ~(static_cast(-1) / static_cast(2));
+  static constexpr T A = MID - (MAX - MID) / 3 * 2;
+  static constexpr T B = MID - (MAX - MID) / 3;
+  static constexpr T C = -B;
+  static constexpr T D = -A;
+
+  static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+"Values shall be in an ascending order");
+};
+
 template  class RangeSetTest : public testing::Test {
 public:
   // Init block
@@ -55,24 +72,11 @@
   using RawRange = std::pair;
   using RawRangeSet = std::initializer_list;
 
-  static constexpr BaseType getMin() {
-return std::numeric_limits::min();
-  }
-  static constexpr BaseType getMax() {
-return std::numeric_limits::max();
-  }
-  static constexpr BaseType getMid() {
-return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
-  }
-
-  static constexpr bool isSigned() { return std::is_signed::value; }
-  static constexpr BaseType fromInt(int X) { return static_cast(X); }
-
-  static llvm::APSInt Base;
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * 8,
+ std::is_unsigned::value};
+Base = X;
+return BVF.getValue(Base);
   }
 
   Range from(const RawRange &Init) {
@@ -160,7 +164,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +172,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -183,29 +210,19 @@
 
 } // namespace
 
-template 
-llvm::APSInt RangeSetTest::Base{sizeof(BaseType) * 8, !isSigned()};
-
 using IntTypes = ::testing::Types;
 TYPED_TEST_CASE(RangeSetTest, IntTypes);
 
 TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
-  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
-
-  constexpr TypeParam MIN = TestFixture::getMin();
-  constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 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");
+  using TV = TestValues;
+  constexpr auto MIN = TV::MIN;
+  constexpr auto MAX = TV::MAX;
+  constexpr auto MID = TV::MID;
+  constexpr auto A = TV::A;
+  constexpr auto B = TV::B;
+  constexpr auto C = TV::C;
+  constexpr auto D = TV::D;
 
   this->checkNegate({{MIN, A}}, {{MIN, MIN}, {D, MAX}});
   this->checkNegate({{MIN, C}}, {{MIN, MIN}, {B, MAX}});
@@ -234,8 +251,9 @@
 }
 
 TYPED_TEST(Ra

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 348284.
ASDenysPetrov added a comment.

@vsavchenko
Reworked the algorithm.

I hope this is the final version. Honestly, I also have the most optimized 
version but it has twice more similar(but different) code and gotos. I decided 
not to present it. Let it be less micro-optimized but much readable version.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -41,6 +41,23 @@
 
 namespace {
 
+template  struct TestValues {
+  static constexpr T MIN = std::numeric_limits::min();
+  static constexpr T MAX = std::numeric_limits::max();
+  // 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).
+  static constexpr T MID =
+  std::is_signed::value ? 0 : ~(static_cast(-1) / static_cast(2));
+  static constexpr T A = MID - (MAX - MID) / 3 * 2;
+  static constexpr T B = MID - (MAX - MID) / 3;
+  static constexpr T C = -B;
+  static constexpr T D = -A;
+
+  static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+"Values shall be in an ascending order");
+};
+
 template  class RangeSetTest : public testing::Test {
 public:
   // Init block
@@ -55,24 +72,11 @@
   using RawRange = std::pair;
   using RawRangeSet = std::initializer_list;
 
-  static constexpr BaseType getMin() {
-return std::numeric_limits::min();
-  }
-  static constexpr BaseType getMax() {
-return std::numeric_limits::max();
-  }
-  static constexpr BaseType getMid() {
-return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
-  }
-
-  static constexpr bool isSigned() { return std::is_signed::value; }
-  static constexpr BaseType fromInt(int X) { return static_cast(X); }
-
-  static llvm::APSInt Base;
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * 8,
+ std::is_unsigned::value};
+Base = X;
+return BVF.getValue(Base);
   }
 
   Range from(const RawRange &Init) {
@@ -160,7 +164,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +172,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -183,29 +210,19 @@
 
 } // namespace
 
-template 
-llvm::APSInt RangeSetTest::Base{sizeof(BaseType) * 8, !isSigned()};
-
 using IntTypes = ::testing::Types;
 TYPED_TEST_CASE(RangeSetTest, IntTypes);
 
 TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
-  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
-
-  constexpr TypeParam MIN = TestFixture::getMin();
-  constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 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");
+  using TV = TestValues;
+  constexpr auto MIN = TV::MIN;
+  constexpr auto MAX = TV::MAX;
+  constexpr auto MID = TV::MID;
+  constexpr auto A = TV::A;
+  constexpr a

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added inline comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:257
+  // BoundCounter is 0 for outer `)`.
+  // BoundCounter is 1 for outer '(' or inner `)`.
+  // BoundCounter is 2 for inner `(`.

vsavchenko wrote:
> ASDenysPetrov wrote:
> > vsavchenko wrote:
> > > nit: it has different ticks than you use in all other places
> > I'm sorry. I didn't get it. What do you mean?
> This is a super duper tiny thing: you usually write `)` or `(`, but here 
> wrote '('.
Oh! :-) Sharp eye!


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Valeriy Savchenko via Phabricator via cfe-commits]

vsavchenko added inline comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:257
+  // BoundCounter is 0 for outer `)`.
+  // BoundCounter is 1 for outer '(' or inner `)`.
+  // BoundCounter is 2 for inner `(`.

ASDenysPetrov wrote:
> vsavchenko wrote:
> > nit: it has different ticks than you use in all other places
> I'm sorry. I didn't get it. What do you mean?
This is a super duper tiny thing: you usually write `)` or `(`, but here wrote 
'('.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added a comment.

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




Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:257
+  // BoundCounter is 0 for outer `)`.
+  // BoundCounter is 1 for outer '(' or inner `)`.
+  // BoundCounter is 2 for inner `(`.

vsavchenko wrote:
> nit: it has different ticks than you use in all other places
I'm sorry. I didn't get it. What do you mean?


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Valeriy Savchenko via Phabricator via cfe-commits]

vsavchenko added a comment.

To be honest, I don't think that it solves the problem I mentioned before.  The 
fact that conditions and branching are part of `operator++` now, doesn't cancel 
them.  I noticed that you made the first loop, so we don't need to check for 
`Min` in the main loop, and this is the right direction. But this approach has 
the same problem as one of the previous methods - you check `isFrom`, this is 
the price of abstraction. This is something that we won't be doing when working 
outside of such abstractions. Also, when one of the range sets is shorter, you 
will keep checking if the other iterator is end on every iteration when you run 
out of the ranges in shorter set.

I'm sorry for being so hard on you about this patch. 😔




Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:257
+  // BoundCounter is 0 for outer `)`.
+  // BoundCounter is 1 for outer '(' or inner `)`.
+  // BoundCounter is 2 for inner `(`.

nit: it has different ticks than you use in all other places


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 347662.
ASDenysPetrov added a comment.

More minor improvements in unit tests.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -41,6 +41,23 @@
 
 namespace {
 
+template  struct TestValues {
+  static constexpr T MIN = std::numeric_limits::min();
+  static constexpr T MAX = std::numeric_limits::max();
+  // 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).
+  static constexpr T MID =
+  std::is_signed::value ? 0 : ~(static_cast(-1) / static_cast(2));
+  static constexpr T A = MID - (MAX - MID) / 3 * 2;
+  static constexpr T B = MID - (MAX - MID) / 3;
+  static constexpr T C = -B;
+  static constexpr T D = -A;
+
+  static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+"Values shall be in an ascending order");
+};
+
 template  class RangeSetTest : public testing::Test {
 public:
   // Init block
@@ -55,24 +72,11 @@
   using RawRange = std::pair;
   using RawRangeSet = std::initializer_list;
 
-  static constexpr BaseType getMin() {
-return std::numeric_limits::min();
-  }
-  static constexpr BaseType getMax() {
-return std::numeric_limits::max();
-  }
-  static constexpr BaseType getMid() {
-return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
-  }
-
-  static constexpr bool isSigned() { return std::is_signed::value; }
-  static constexpr BaseType fromInt(int X) { return static_cast(X); }
-
-  static llvm::APSInt Base;
   const llvm::APSInt &from(BaseType X) {
-llvm::APSInt Dummy = Base;
-Dummy = X;
-return BVF.getValue(Dummy);
+static llvm::APSInt Base{sizeof(BaseType) * 8,
+ std::is_unsigned::value};
+Base = X;
+return BVF.getValue(Base);
   }
 
   Range from(const RawRange &Init) {
@@ -160,7 +164,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +172,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -183,29 +210,19 @@
 
 } // namespace
 
-template 
-llvm::APSInt RangeSetTest::Base{sizeof(BaseType) * 8, !isSigned()};
-
 using IntTypes = ::testing::Types;
 TYPED_TEST_CASE(RangeSetTest, IntTypes);
 
 TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
-  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
-
-  constexpr TypeParam MIN = TestFixture::getMin();
-  constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 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");
+  using TV = TestValues;
+  constexpr auto MIN = TV::MIN;
+  constexpr auto MAX = TV::MAX;
+  constexpr auto MID = TV::MID;
+  constexpr auto A = TV::A;
+  constexpr auto B = TV::B;
+  constexpr auto C = TV::C;
+  constexpr auto D = TV::D;
 
   this->checkNegate({{MIN, A}}, {{MIN, MIN}, {D, MAX}});
   this->checkNegate({{MIN, C}}, {{MIN, MIN}, {B, MAX}});
@@ -234,8 +251,9 @@
 }
 
 TYPED_TEST(Ran

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 347658.
ASDenysPetrov added a comment.

Minor improvements in unit tests.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -41,6 +41,23 @@
 
 namespace {
 
+template  struct TestValues {
+  static constexpr T MIN = std::numeric_limits::min();
+  static constexpr T MAX = std::numeric_limits::max();
+  // 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).
+  static constexpr T MID =
+  std::is_signed::value ? 0 : ~(static_cast(-1) / static_cast(2));
+  static constexpr T A = MID - (MAX - MID) / 3 * 2;
+  static constexpr T B = MID - (MAX - MID) / 3;
+  static constexpr T C = -B;
+  static constexpr T D = -A;
+
+  static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+"Values shall be in an ascending order");
+};
+
 template  class RangeSetTest : public testing::Test {
 public:
   // Init block
@@ -55,18 +72,14 @@
   using RawRange = std::pair;
   using RawRangeSet = std::initializer_list;
 
-  static constexpr BaseType getMin() {
-return std::numeric_limits::min();
-  }
-  static constexpr BaseType getMax() {
-return std::numeric_limits::max();
-  }
-  static constexpr BaseType getMid() {
-return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
-  }
-
-  static constexpr bool isSigned() { return std::is_signed::value; }
-  static constexpr BaseType fromInt(int X) { return static_cast(X); }
+  using TV = TestValues;
+  static constexpr auto MIN = TV::MIN;
+  static constexpr auto MAX = TV::MAX;
+  static constexpr auto MID = TV::MID;
+  static constexpr auto A = TV::A;
+  static constexpr auto B = TV::B;
+  static constexpr auto C = TV::C;
+  static constexpr auto D = TV::D;
 
   static llvm::APSInt Base;
   const llvm::APSInt &from(BaseType X) {
@@ -160,7 +173,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +181,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -184,7 +220,8 @@
 } // namespace
 
 template 
-llvm::APSInt RangeSetTest::Base{sizeof(BaseType) * 8, !isSigned()};
+llvm::APSInt RangeSetTest::Base{sizeof(BaseType) * 8,
+  std::is_unsigned::value};
 
 using IntTypes = ::testing::Types;
@@ -192,17 +229,13 @@
 
 TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
   // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
-
-  constexpr TypeParam MIN = TestFixture::getMin();
-  constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 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;
+  constexpr TypeParam MIN = TestFixture::MIN;
+  constexpr TypeParam MAX = TestFixture::MAX;
+  constexpr TypeParam MID = TestFixture::MID;
+  constexpr TypeParam A = TestFixture::A;
+  constexpr TypeParam B = TestFixture::B;
+  constexpr TypeParam C = TestFixture::C;
+  constexpr TypeParam D = TestFixture::D;
 
   static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
 "Values shall be in an a

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 346741.
ASDenysPetrov added a comment.
Herald added a subscriber: manas.

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


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -61,6 +61,9 @@
   static constexpr BaseType getMax() {
 return std::numeric_limits::max();
   }
+  // 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).
   static constexpr BaseType getMid() {
 return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
   }
@@ -160,7 +163,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +171,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -195,9 +221,6 @@
 
   constexpr TypeParam MIN = TestFixture::getMin();
   constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 TypeParam MID = TestFixture::getMid();
   constexpr TypeParam A = MID - TestFixture::fromInt(42 + 42);
   constexpr TypeParam B = MID - TestFixture::fromInt(42);
@@ -347,3 +370,210 @@
   // 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}});
 }
+
+TYPED_TEST(RangeSetTest, RangeSetUniteTest) {
+
+  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
+  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;
+
+  // LHS and RHS is empty.
+  // RHS =>
+  // LHS => =
+  //___   ___
+  this->checkUnite({}, {}, {});
+
+  // RHS is empty.
+  // RHS =>
+  // LHS =>_=_
+  //__/_\__   __/_\__
+  this->checkUnite({{A, B}}, {}, {{A, B}});
+  this->checkUnite({{A, B}, {C, D}}, {}, {{A, B}, {C, D}});
+  this->checkUnite({{MIN, MIN}}, {}, {{MIN, MIN}});
+  this->checkUnite({{MAX, MAX}}, {}, {{MAX, MAX}});
+  this->checkUnite({{MIN, MIN}, {MAX, MAX}}, {}, {{MIN, MIN}, {MAX, MAX}});
+
+  // LHS is empty.
+  // RHS => ___
+  // LHS =>/   \=_
+  //__/_\__   __/_\__
+  this->checkUnite({}, B, {{B, B}});
+  this->checkUnite({}, {B, C}, {{B, C}});
+  this->checkUnite({}, {{MIN, B}, {C, MAX}}, {{MIN, B}, {C, MAX}});
+  this->checkUnite({}, {{MIN, MIN}}, {{MIN, MIN}});
+  this->checkUnite({}, {{MAX, MAX}}, {{MAX, MAX}});
+  this->checkUnite({}, {{MIN, MIN}, {MAX, MAX}}, {{MIN, MIN}, {MAX, MAX}});
+
+  // RHS is detached from LHS.
+  // RHS => ___
+  // LHS =>___ /   \=___ _
+  //__/___\___/_\__   __/___\___/_\__
+  this->checkUnite({{A, C}}, D, {{A, C}, {D, D}});
+  this->checkUnite({{MID, C}, {D, MAX}}, A, {{A, A}, {MID, C}, {D, MAX}});
+  this->checkUn

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Valeriy Savchenko via Phabricator via cfe-commits]

vsavchenko added inline comments.



Comment at: 
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h:250
+/// guarantee this.
+ContainerType unite(const ContainerType &LHS, const ContainerType &RHS);
 

ASDenysPetrov wrote:
> vsavchenko wrote:
> > `ContainerType` is basically a mutable version of `RangeSet`, so there is 
> > only one reason to return it - you believe that the users might want to 
> > modify it after they called this `unite`.  But as long as this `unite` is 
> > just a generalized version of user-facing `unites, it can totally return 
> > `RangeSet`.
> I'm going to use raw ContainerType in further patches. So this is exactly 
> what I want.
Oh, I see. OK then :)


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added a comment.

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




Comment at: 
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h:250
+/// guarantee this.
+ContainerType unite(const ContainerType &LHS, const ContainerType &RHS);
 

vsavchenko wrote:
> `ContainerType` is basically a mutable version of `RangeSet`, so there is 
> only one reason to return it - you believe that the users might want to 
> modify it after they called this `unite`.  But as long as this `unite` is 
> just a generalized version of user-facing `unites, it can totally return 
> `RangeSet`.
I'm going to use raw ContainerType in further patches. So this is exactly what 
I want.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:221
+  Result.append(B, E);
+
+  return Result;

vsavchenko wrote:
> Oof, I don't know about this algorithm.  I mean it does its job.  But IMO it 
> lacks a good description of what are the invariants and what are the 
> different situations we are looking for.
> Aaaand you kind of re-check certain conditions multiple times.  One example 
> here is the check for `Min` and `Max`. Those situations are super rare, but 
> we check for them on every single iteration. `std::min` and `std::max` are 
> additional comparisons.  As I mentioned before, constant factor is the key 
> here and less comparisons we do is way more important than doing binary 
> search at some point.
> Just make a benchmark if you don't believe me (with google-benchmark, for 
> example).  The version with less comparisons will dominate one with more on 
> `RangeSet` under 20 (and they'll be even smaller in practice).
I'll investigate the whole algorithm once more and reduce comparisons.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Valeriy Savchenko via Phabricator via cfe-commits]

vsavchenko added inline comments.



Comment at: 
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h:147
+/// where N = size(LHS), M = size(RHS)
+RangeSet unite(RangeSet Original, RangeSet RHS);
+/// Create a new set by uniting given range set with the given range.

`LHS`



Comment at: 
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h:247
 RangeSet intersect(const ContainerType &LHS, const ContainerType &RHS);
+/// NOTE: This function relies that all values in the containers are
+/// persistent (created via BasicValueFactory::getValue). User shall

nit: "...on the fact that..."



Comment at: 
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h:250
+/// guarantee this.
+ContainerType unite(const ContainerType &LHS, const ContainerType &RHS);
 

`ContainerType` is basically a mutable version of `RangeSet`, so there is only 
one reason to return it - you believe that the users might want to modify it 
after they called this `unite`.  But as long as this `unite` is just a 
generalized version of user-facing `unites, it can totally return `RangeSet`.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:112
+RangeSet RangeSet::Factory::add(RangeSet LHS, RangeSet RHS) {
+  ContainerType Result;
+  std::merge(LHS.begin(), LHS.end(), RHS.begin(), RHS.end(),

Let's reserve some place here.  Because `LHS` and `RHS` don't have 
intersections, the result always has `size(LHS) + size(RHS)` elements



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:221
+  Result.append(B, E);
+
+  return Result;

Oof, I don't know about this algorithm.  I mean it does its job.  But IMO it 
lacks a good description of what are the invariants and what are the different 
situations we are looking for.
Aaaand you kind of re-check certain conditions multiple times.  One example 
here is the check for `Min` and `Max`. Those situations are super rare, but we 
check for them on every single iteration. `std::min` and `std::max` are 
additional comparisons.  As I mentioned before, constant factor is the key here 
and less comparisons we do is way more important than doing binary search at 
some point.
Just make a benchmark if you don't believe me (with google-benchmark, for 
example).  The version with less comparisons will dominate one with more on 
`RangeSet` under 20 (and they'll be even smaller in practice).


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 34.
ASDenysPetrov added a comment.

Minor performance improvement. Add more comments.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -61,6 +61,9 @@
   static constexpr BaseType getMax() {
 return std::numeric_limits::max();
   }
+  // 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).
   static constexpr BaseType getMid() {
 return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
   }
@@ -160,7 +163,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +171,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -195,9 +221,6 @@
 
   constexpr TypeParam MIN = TestFixture::getMin();
   constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 TypeParam MID = TestFixture::getMid();
   constexpr TypeParam A = MID - TestFixture::fromInt(42 + 42);
   constexpr TypeParam B = MID - TestFixture::fromInt(42);
@@ -347,3 +370,201 @@
   // 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}});
 }
+
+TYPED_TEST(RangeSetTest, RangeSetUniteTest) {
+
+  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
+  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;
+
+  // LHS and RHS is empty.
+  // RHS =>
+  // LHS => =
+  //___   ___
+  this->checkUnite({}, {}, {});
+
+  // RHS is empty.
+  // RHS =>
+  // LHS =>_=_
+  //__/_\__   __/_\__
+  this->checkUnite({{A, B}}, {}, {{A, B}});
+  this->checkUnite({{A, B}, {C, D}}, {}, {{A, B}, {C, D}});
+
+  // LHS is empty.
+  // RHS => ___
+  // LHS =>/   \=_
+  //__/_\__   __/_\__
+  this->checkUnite({}, B, {{B, B}});
+  this->checkUnite({}, {B, C}, {{B, C}});
+  this->checkUnite({}, {{MIN, B}, {C, MAX}}, {{MIN, B}, {C, MAX}});
+
+  // RHS is detached from LHS.
+  // RHS => ___
+  // LHS =>___ /   \=___ _
+  //__/___\___/_\__   __/___\___/_\__
+  this->checkUnite({{A, C}}, D, {{A, C}, {D, D}});
+  this->checkUnite({{MID, C}, {D, MAX}}, A, {{A, A}, {MID, C}, {D, MAX}});
+  this->checkUnite({{A, B}}, {MID, D}, {{A, B}, {MID, D}});
+  this->checkUnite({{MIN, A}, {D, MAX}}, {B, C}, {{MIN, A}, {B, C}, {D, MAX}});
+  this->checkUnite({{B, MID}, {D, MAX}}, {{MIN, A}, {C, C}},
+   {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+  this->checkUnite({{MIN, A}, {C, C}}, {{B, MID}, {D, MAX}},
+   {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+  this->checkUnite({{MAX, MAX}}, {A, B}, {{A, B}, {MAX, MAX}});
+  this->checkUnite({{MIN, MIN}}, {A, B}, {{MIN, MIN}, {A, B}});
+
+  // RHS is inside LHS.
+  // RHS => ___
+  // LHS

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 343750.
ASDenysPetrov added a comment.

Minor comment fix.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -61,6 +61,9 @@
   static constexpr BaseType getMax() {
 return std::numeric_limits::max();
   }
+  // 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).
   static constexpr BaseType getMid() {
 return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
   }
@@ -160,7 +163,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +171,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -195,9 +221,6 @@
 
   constexpr TypeParam MIN = TestFixture::getMin();
   constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 TypeParam MID = TestFixture::getMid();
   constexpr TypeParam A = MID - TestFixture::fromInt(42 + 42);
   constexpr TypeParam B = MID - TestFixture::fromInt(42);
@@ -347,3 +370,201 @@
   // 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}});
 }
+
+TYPED_TEST(RangeSetTest, RangeSetUniteTest) {
+
+  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
+  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;
+
+  // LHS and RHS is empty.
+  // RHS =>
+  // LHS => =
+  //___   ___
+  this->checkUnite({}, {}, {});
+
+  // RHS is empty.
+  // RHS =>
+  // LHS =>_=_
+  //__/_\__   __/_\__
+  this->checkUnite({{A, B}}, {}, {{A, B}});
+  this->checkUnite({{A, B}, {C, D}}, {}, {{A, B}, {C, D}});
+
+  // LHS is empty.
+  // RHS => ___
+  // LHS =>/   \=_
+  //__/_\__   __/_\__
+  this->checkUnite({}, B, {{B, B}});
+  this->checkUnite({}, {B, C}, {{B, C}});
+  this->checkUnite({}, {{MIN, B}, {C, MAX}}, {{MIN, B}, {C, MAX}});
+
+  // RHS is detached from LHS.
+  // RHS => ___
+  // LHS =>___ /   \=___ _
+  //__/___\___/_\__   __/___\___/_\__
+  this->checkUnite({{A, C}}, D, {{A, C}, {D, D}});
+  this->checkUnite({{MID, C}, {D, MAX}}, A, {{A, A}, {MID, C}, {D, MAX}});
+  this->checkUnite({{A, B}}, {MID, D}, {{A, B}, {MID, D}});
+  this->checkUnite({{MIN, A}, {D, MAX}}, {B, C}, {{MIN, A}, {B, C}, {D, MAX}});
+  this->checkUnite({{B, MID}, {D, MAX}}, {{MIN, A}, {C, C}},
+   {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+  this->checkUnite({{MIN, A}, {C, C}}, {{B, MID}, {D, MAX}},
+   {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+  this->checkUnite({{MAX, MAX}}, {A, B}, {{A, B}, {MAX, MAX}});
+  this->checkUnite({{MIN, MIN}}, {A, B}, {{MIN, MIN}, {A, B}});
+
+  // RHS is inside LHS.
+  // RHS => ___
+  // LHS => ___/___\___ = _

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added inline comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:136
+
+RangeSet RangeSet::Factory::unite(RangeSet LHS, RangeSet RHS) {
+  if (LHS.isEmpty())

vsavchenko wrote:
> I'd prefer `merge`
There are common namings of operations with sets and `union` is one of them. 
IMO this is most appropriate one.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 343714.
ASDenysPetrov added a comment.

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


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -61,6 +61,9 @@
   static constexpr BaseType getMax() {
 return std::numeric_limits::max();
   }
+  // 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).
   static constexpr BaseType getMid() {
 return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
   }
@@ -160,7 +163,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +171,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -195,9 +221,6 @@
 
   constexpr TypeParam MIN = TestFixture::getMin();
   constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 TypeParam MID = TestFixture::getMid();
   constexpr TypeParam A = MID - TestFixture::fromInt(42 + 42);
   constexpr TypeParam B = MID - TestFixture::fromInt(42);
@@ -347,3 +370,201 @@
   // 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}});
 }
+
+TYPED_TEST(RangeSetTest, RangeSetUniteTest) {
+
+  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
+  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;
+
+  // LHS and RHS is empty.
+  // RHS =>
+  // LHS => =
+  //___   ___
+  this->checkUnite({}, {}, {});
+
+  // RHS is empty.
+  // RHS =>
+  // LHS =>_=_
+  //__/_\__   __/_\__
+  this->checkUnite({{A, B}}, {}, {{A, B}});
+  this->checkUnite({{A, B}, {C, D}}, {}, {{A, B}, {C, D}});
+
+  // LHS is empty.
+  // RHS => ___
+  // LHS =>/   \=_
+  //__/_\__   __/_\__
+  this->checkUnite({}, B, {{B, B}});
+  this->checkUnite({}, {B, C}, {{B, C}});
+  this->checkUnite({}, {{MIN, B}, {C, MAX}}, {{MIN, B}, {C, MAX}});
+
+  // RHS is detached from LHS.
+  // RHS => ___
+  // LHS =>___ /   \=___ _
+  //__/___\___/_\__   __/___\___/_\__
+  this->checkUnite({{A, C}}, D, {{A, C}, {D, D}});
+  this->checkUnite({{MID, C}, {D, MAX}}, A, {{A, A}, {MID, C}, {D, MAX}});
+  this->checkUnite({{A, B}}, {MID, D}, {{A, B}, {MID, D}});
+  this->checkUnite({{MIN, A}, {D, MAX}}, {B, C}, {{MIN, A}, {B, C}, {D, MAX}});
+  this->checkUnite({{B, MID}, {D, MAX}}, {{MIN, A}, {C, C}},
+   {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+  this->checkUnite({{MIN, A}, {C, C}}, {{B, MID}, {D, MAX}},
+   {{MIN, A}, {B, MID}, {C, C}, {D, MAX}});
+  this->checkUnite({{MAX, MAX}}, {A, B}, {{A, B}, {MAX, MAX}});
+  this->checkUnite({{MIN, MIN}}, {A, B}, {{MIN, MIN}, {A, B}});
+
+  // RHS is inside L

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov added a comment.

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

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

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

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


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Valeriy Savchenko via Phabricator via cfe-commits]

vsavchenko added inline comments.



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:471
+
+  // RHS adjacent to LHS in between.
+  // RHS => ___

I guess I also want to have more cases where ranges from RHS are in between 
ranges from LHS, also it should be a case with LHS being a set of ranges.



Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:497
+  this->checkUnite({{MIN, B}, {C, MAX}}, {{A, D}}, {{MIN, MAX}});
+}

Also I'd like to see cases when there are ranges to merge from two sets but 
then one set has a bunch of other ranges that should be added as is.  We can 
automatically think of two possibilities here: when these additional ranges are 
before and after the common part.
And I guess I want at least one check with two sets with a good amount of 
ranges in both covering all possible situations and overlappings.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Valeriy Savchenko via Phabricator via cfe-commits]

vsavchenko added a comment.

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




Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:136
+
+RangeSet RangeSet::Factory::unite(RangeSet LHS, RangeSet RHS) {
+  if (LHS.isEmpty())

I'd prefer `merge`



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:217
+
+  while (BIt1 || BIt2) {
+

This algorithm is indeed `O(N +M)`, good job!
But let me get picky again 😅

It looks like we do too many comparisons in this loop.  As I said earlier, 
constant factor is the key here and while this iterator idea is good it is a 
tradeoff. There is a piece of knowledge that would've been obvious with regular 
iterators, now is a run-time unknown that we constantly need to check (`isTo` 
and `isFrom`).

What we are trying to achieve here is not harder than what we do in `intersect` 
and there it is way less comparisons.  While iterating through sets we can keep 
a set of invariants, so we don't need to re-check something that we already 
know.

Here is a sketch for the algorithm:

```
{
  assert(First != FirstEnd && Second != SecondEnd);
  // We have && here because one of them reaches its end,
  // we should not check for it again and simply add the rest
  // of the other set.
  while (true) {
// We need to find the beginning of the next range to add
// First should be the iterator which To is a candidate to be
// an and for the merged range.
if (First.From() > Second.From()) {
  swap();
}

auto From = First.From();

// That's it, we found our start, and we need to go through
// other ranges and look for the end.
// After this point, First.From() shouldn'y be accessed.

while (true) {
  // We can compress all the checks into just one.
  // This essentially means that Second should not get merged with First.
  if (Second.From() > First.To() + 1) {
break;
  }

  if (Second.From() > First.From()) {
// First is maintained as a candidate for the end.
swap();
  }

  // At this point we know that Second lives fully inside
  // of the new range and we can skip it.
  ++Second;

  // If we have nothing else in the second set...
  if (Second == SecondEnd) {
// ...let's finish the current range first...
Result.emplace_back(From, First.To());
while (++First != FirstEnd) {
  // ...and copy the rest of the ranges
  Result.push_back(*First);
}
// The range is ready.
return makePersistent(Result);
  }
};

// Second is outside of the range, and we can
// safely add a new range.
Result.emplace_back(From, First.To());
++First;

// First set can be over at this point and we should...
if (First == FirstEnd) {
  // ...copy the rest if the second set's ranges.
  while (Second != SecondEnd) {
Result.push_back(*(Second++));
  }
  // Nothing left to do.
  return makePersistent(Result);
}
  };

  // No way for us to get here!
  llvm_unreachable("...");
}
```

It's trickier in the way we end things than the intersection because we still 
need to add the rest of the other set.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:279-293
+  auto It = std::lower_bound(
+  B, E, Range(Point), [&Max, &One](const Range &OrigR, const Range &R) {
+return OrigR.To() != Max && (OrigR.To() + One) < R.From();
+  });
+
+  if (It != E && It->Includes(Point))
+return Original;

I don't see any practical reasons to keep this version over the more generic 
`RangeSet` + `RangeSet`



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:321-335
+
+  const APSInt &F = (It == E) ? R.From() : std::min(R.From(), It->From());
+
+  // Find a right part of disjoint ranges from the new range.
+  It = std::lower_bound(
+  It, E, R, [&One, &Max](const Range &OrigR, const Range &R) {
+return OrigR.From() == Max || (OrigR.From() - One) <= R.To();

Same here, it is just way more code to maintain.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

[Denys Petrov via Phabricator via cfe-commits]

ASDenysPetrov updated this revision to Diff 335768.
ASDenysPetrov retitled this revision from "[analyzer] Handle intersections and 
adjacency in RangeSet::Factory::add function" to "[analyzer] Implemented 
RangeSet::Factory::unite function to handle intersections and adjacency".
ASDenysPetrov added a comment.

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

@vsavchenko You are welcome to evaluate this changes.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D99797/new/

https://reviews.llvm.org/D99797

Files:
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/unittests/StaticAnalyzer/RangeSetTest.cpp

Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -61,6 +61,9 @@
   static constexpr BaseType getMax() {
 return std::numeric_limits::max();
   }
+  // 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).
   static constexpr BaseType getMid() {
 return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
   }
@@ -160,7 +163,7 @@
 
   void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
 RawRangeSet RawExpected) {
-wrap(&Self::checkAddImpl, RawRHS, RawLHS, RawExpected);
+wrap(&Self::checkAddImpl, RawLHS, RawRHS, RawExpected);
   }
 
   void checkAdd(RawRangeSet RawLHS, BaseType RawRHS, RawRangeSet RawExpected) {
@@ -168,6 +171,29 @@
  RawExpected);
   }
 
+  template 
+  void checkUniteImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+RangeSet Result = F.unite(LHS, RHS);
+EXPECT_EQ(Result, Expected)
+<< "while uniting " << toString(LHS) << " and " << toString(RHS);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRange RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, RawRangeSet RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS, RawExpected);
+  }
+
+  void checkUnite(RawRangeSet RawLHS, BaseType RawRHS,
+  RawRangeSet RawExpected) {
+wrap(&Self::checkUniteImpl, RawLHS, RawRHS,
+ RawExpected);
+  }
+
   void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
RangeSet Expected) {
 RangeSet Result = F.deletePoint(From, Point);
@@ -195,9 +221,6 @@
 
   constexpr TypeParam MIN = TestFixture::getMin();
   constexpr TypeParam MAX = TestFixture::getMax();
-  // 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 TypeParam MID = TestFixture::getMid();
   constexpr TypeParam A = MID - TestFixture::fromInt(42 + 42);
   constexpr TypeParam B = MID - TestFixture::fromInt(42);
@@ -347,3 +370,128 @@
   // 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}});
 }
+
+TYPED_TEST(RangeSetTest, RangeSetUniteTest) {
+
+  // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
+  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;
+
+  // LHS and RHS is empty.
+  // RHS =>
+  // LHS => =
+  //___   ___
+  this->checkUnite({}, {}, {});
+
+  // RHS is empty.
+  // RHS =>
+  // LHS =>_=_
+  //__/_\__   __/_\__
+  this->checkUnite({{A, B}}, {}, {{A, B}});
+  this->checkUnite({{A, B}, {C, D}}, {}, {{A, B}, {C, D}});
+
+  // LHS is empty.
+  // RHS => ___
+  // LHS =>/   \=_
+  //__/_\__   __/_\__
+  this->checkUnite({}, B, {{B, B}});
+  this->checkUnite({}, {B, C}, {{B, C}});
+  this->checkUnite({}, {{MIN, B}, {C, MAX}}, {{MIN, B}, {C, MAX}});
+
+  // RHS is detached from LHS.
+  // RHS => ___
+  // LHS =>___ /   \=___ _
+  //__/___\___/_\__   __/___\___/_\__
+  this->checkUnite({{A, C}}, D, {{A, C}, {D, D}});
+  this->checkUnite({{MID, C}, {D, MAX}}, A, {{A, A}, {MID, C}, {D, MAX}});
+  this->checkUnite({{A, B}}, {MID, D}, {{A, B}, {MID, D}});
+  this->checkUnite({{MIN, A}, {D, MAX}}, {B, C}, {{MIN, A}, {B, C}, {D, MAX}});
+  this->checkUnite({{B, MID}, {D,