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

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

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

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:

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

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.

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

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] D99797: [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency

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

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

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

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

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()) +

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

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

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

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: +

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

ASDenysPetrov added inline comments. Comment at: clang/unittests/StaticAnalyzer/RangeSetTest.cpp:81 const llvm::APSInt (BaseType X) { -llvm::APSInt Dummy = Base; -Dummy = X; -return BVF.getValue(Dummy); +static llvm::APSInt Base{sizeof(BaseType) * 8, +

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

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

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

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.

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

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.

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

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:

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

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 (BaseType X) { -llvm::APSInt Dummy = Base; -Dummy = X; -return BVF.getValue(Dummy); +

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

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

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

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:

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

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

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

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

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

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:

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

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.

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

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

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

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:

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

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

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

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

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

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

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

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 +} +

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

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:

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

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.

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

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: >

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

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: >

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

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

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

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

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

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:

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

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:

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

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

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

vsavchenko added inline comments. Comment at: clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h:250 +/// guarantee this. +ContainerType unite(const ContainerType , const ContainerType ); ASDenysPetrov wrote: > vsavchenko

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

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

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

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

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

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:

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

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

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

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

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

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:

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

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

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

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

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

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

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

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