[libcxx][test] Add tests for std::vector comparisons

[kboyarinov]

Summary

Positive and negative tests for std::vector::operator==, !=, <, <=, >, >=

[kboyarinov]

Fix incorrect upload

[rarutyun]

Hi everybody,

We have some amount of patches that increases code coverage of LLVM libc++ and we would like to contribute those. This is the first one.

@kboyarinov is supposed to be the main contributor.

[rarutyun]

libcxx/test/std/containers/sequences/vector/compare.fail.cpp

25 ↗

(On Diff #379429)

you don't disable this test for C++03 but you use vector<something>> without the space between >> that is treated as operator>> for C++ prior 11. We need enable this test starting from C++11 or fix that. Let's see how it's done for other tests and make it consistent.

libcxx/test/std/containers/sequences/vector/compare.pass.cpp

38

You use braced-init-list for std::vector initialization, which, of course, is allowed since C++11. Thus, this test fails on C++03. Need to fix that.

[• Quuxplusone]

libcxx/test/std/containers/sequences/vector/compare.fail.cpp

1 ↗

(On Diff #379429)

@rarutyun wrote:

We have some amount of patches that increases code coverage of LLVM libc++ and we would like to contribute those

My kneejerk reaction to this PR, initially, was "I don't think this adds value," since it's mostly testing the ill-formed cases' diagnostics. But you're saying that this PR increases code coverage according to some measurable metric? Could you elaborate a bit on how you're measuring code coverage (especially for heavily templated code like this)?

libcxx/test/std/containers/sequences/vector/compare.pass.cpp

17

I'd like someone to confirm that this test is still expected to pass in C++20 after vector's operator<=> lands. (@cjdb was working on that a long time ago in D80904.) It would be mildly unfortunate if we had to revisit this test in like a month from now.

libcxx/test/support/test_comparisons.h

201

In isolation, I'd say "please inline these types into the one test file that uses them." But I'm guessing that you're planning to submit similar followup PRs for deque, list, etc. etc., which will also use these types?
Still, these can be simplified:

• I don't see the benefit of the int Dummy parameter in the first two types.
• I don't see the benefit of int second in LessAndEqComp.
• I don't think the cost/benefit ratio is right for the .fail.cpp test; I'd eliminate it.

[kboyarinov]

libcxx/test/std/containers/sequences/vector/compare.pass.cpp

17

I would expect this test to pass when vector::operator<=> will be defined, because according to the standard, such an operator should perform per-element comparison using value_type::operator<=> if it is well-formed or a set of value_type::operator< comparisons. We do not test which operator is called for value_type objects and the result of the comparison should not change when operator<=> will be defined.

libcxx/test/support/test_comparisons.h

201

You are right, we already have a set of patches in progress for other containers and these types will be used to test them.

As for the simplification:

I don't see the benefit of the int Dummy parameter in the first two types.

This parameter is required for negative tests. Consider the following code:

struct NoComparisons {};

std::vector<NoComparisons> v1, v2;
(void)(v1 == v2);
(void)(v1 != v2);

The compiler will indicate that we have he call operator== and operator != for the same instantiation of the vector and according to the fact that operator!= reuses operator==, only one compilation error will be shown.

Dummy template parameter is needed to receive and test separate compilation errors for all comparison operators.

I don't see the benefit of int second in LessAndEqComp.

Agree - it will be removed

I don't think the cost/benefit ratio is right for the .fail.cpp test; I'd eliminate it.

I am not sure that I understood this comment correct. Could you please clarify what you mean with cost/benefit ratio here and what should be eliminated.

Thank you in advance.

[ldionne]

Thanks a lot for looking into this! I was incredibly surprised to learn that we didn't have tests for std::vector's comparison. It's pretty vexing.

If you have similar patches for other container types, it's probably reasonable to fold them into this one (assuming they are all pretty similar).

libcxx/test/std/containers/sequences/vector/compare.fail.cpp

1 ↗

(On Diff #379429)

@Quuxplusone I mean, the negative comparison test we can have a discussion about, but the positive test is definitely increasing coverage. I was surprised when I was unable to find tests for vector's comparison operators, and it seems like indeed we didn't have any before this patch.

@rarutyun Regarding the negative tests, what Arthur is saying is that we don't normally assert the ill-formedness of things. On reason is that there's almost always an infinite number of ways a program can be ill-formed, so where do you stop? If the Standard did specify that operator==(vector<T>, vector<U>) does not participate in overload resolution if T and U are not comparable, then we'd test that. But as it is, the fact that T and U are Cpp17EqualityComparable is a precondition (http://eel.is/c++draft/description#structure.specifications-3.3), which means that it's technically UB to perform the comparisons you do below.

I think my preferred approach here would be to drop the negative tests but definitely keep the positive ones.

libcxx/test/std/containers/sequences/vector/compare.pass.cpp

2

Is it possible that you've made these files executable? See the File Mode diff above.

[kboyarinov]

"c++03fication" of the tests

[Mordante]

Thanks for working on this!

libcxx/test/std/containers/sequences/vector/compare.fail.cpp

1 ↗

(On Diff #379429)

@rarutyun I'm also interested to learn more about how you measured the coverage. The coverage available at http://lab.llvm.org:8080/coverage/coverage-reports/index.html misses a lot of files and I'm not convinced the values it shows are correct. So I would be very interested to get the correct values.

libcxx/test/std/containers/sequences/vector/compare.pass.cpp

118

Please add a return 0;. We require this for main since some platforms require this and we like to keep our tests portable.

[rarutyun]

In D111738#3063968, @ldionne wrote:

Thanks a lot for looking into this! I was incredibly surprised to learn that we didn't have tests for std::vector's comparison. It's pretty vexing.

@ldionne Yep, no problem.

If you have similar patches for other container types, it's probably reasonable to fold them into this one (assuming they are all pretty similar).

Actually as I mentioned in one of the comments we expect to have relatively big amount of patches that increase code coverage. We just decided to start with containers but eventually our code changes that help with code coverage are not limited to containers functionality.

Some patches for containers are similar, others are not. We tried to keep those relatively small and comfortable for review. Even if some of them would be similar for deque, list, etc. our preference is to keep those small enough and well decomposable. If you have strong preference we may try to fold them into one but I believe it likely slows down the things.

libcxx/test/std/containers/sequences/vector/compare.fail.cpp

1 ↗

(On Diff #379429)

Could you elaborate a bit on how you're measuring code coverage (especially for heavily templated code like this)?

@Quuxplusone Sure. We used BullsEye tool. For the template code it tracks that template was instantiated at least once (with any type) and called. If, of course, you have partial template specialization for the class and this specialization has its own functions all those won't be covered unless you instantiate the class to match on that partial specialization and call the method you want to cover.
Then, this tool as usual makes sure that all branches within the function are covered. Nothing special IIRC.

The coverage available at http://lab.llvm.org:8080/coverage/coverage-reports/index.html

@Mordante What I see in the report above (if I looked correctly) it does not cover include/ folder, only src/ one. Thus, I believe many things might be missed. We kind of build the tests and then just say that we need include/ folder to be covered. This is very high level view of how we do it. I don't have particular technical details on my hand right now.

So I would be very interested to get the correct values.

We believe in those numbers we got but this tool has drawback, though (as well as all tools we tried). It cannot instrument constexpr functions because it injects some special code within the body of the function that does not fulfill constexpr requirements. As the result BullsEye just ignores such functions.

We have got an idea to remove constexpr with some script on the fly just to collect code coverage metrics but as you may guess it doesn't work so easy because constexpr functions could be called in a context where constant expression is required (e.g. template instantiation of non-type template parameter) . With such approach applied the code just fails to compile in some circumstances.

1 ↗

(On Diff #379429)

I think my preferred approach here would be to drop the negative tests but definitely keep the positive ones.

Ok I see you point. Basically you are saying that negative tests are good for Constaints but do not bring much value for preconditions Preconditions. That makes perfect sense to me. Now I better understand the criteria.

For further patches we would keep it in mind but if something that tests Preconditions remains please let us know.

[Mordante]

libcxx/test/std/containers/sequences/vector/compare.fail.cpp

1 ↗

(On Diff #379429)

The coverage available at http://lab.llvm.org:8080/coverage/coverage-reports/index.html

@Mordante What I see in the report above (if I looked correctly) it does not cover include/ folder, only src/ one.

Indeed, but even the src/ looks odd.

So I would be very interested to get the correct values.

We believe in those numbers we got but this tool has drawback, though (as well as all tools we tried). It cannot instrument constexpr functions because it injects some special code within the body of the function that does not fulfill constexpr requirements. As the result BullsEye just ignores such functions.

Thanks for the information!

[kboyarinov]

Remove negative tests because EqualityComparable is a Precondition for std::vector::operator==. Violation of the precondition results in undefined behavior => the fact that the program is ill-formed is not guaranteed by the standard and should not be tested.

[ldionne]

In D111738#3067720, @rarutyun wrote:

Actually as I mentioned in one of the comments we expect to have relatively big amount of patches that increase code coverage.

Awesome.

Some patches for containers are similar, others are not. We tried to keep those relatively small and comfortable for review.

I'm happy with whatever makes you happy!

Do you need help committing the patch? If so, please provide Author Name <email@domain> for me to commit this on your behalf. Also you should get commit access per https://releases.llvm.org/9.0.0/docs/DeveloperPolicy.html#obtaining-commit-access if you plan on submitting more of these fixes. Thanks!

[rarutyun]

Do you need help committing the patch? If so, please provide Author Name <email@domain> for me to commit this on your behalf. Also you should get commit access per https://releases.llvm.org/9.0.0/docs/DeveloperPolicy.html#obtaining-commit-access if you plan on submitting more of these fixes. Thanks!

I was planning to get the commit rights a while ago. I believe the time has come. So let me ask for the access and pass this quest myself.

libcxx/test/std/containers/sequences/vector/compare.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <vector>
+
+// bool operator==(const vector& lhs, const vector& rhs);
+// bool operator!=(const vector& lhs, const vector& rhs);
+// bool operator< (const vector& lhs, const vector& rhs);
+// bool operator<=(const vector& lhs, const vector& rhs);
+// bool operator> (const vector& lhs, const vector& rhs);
+// bool operator>=(const vector& lhs, const vector& rhs);
+
+#include <vector>
+#include <cassert>
+
+#include "test_comparisons.h"
+
+int main(int, char**) {
+    {
+        const std::vector<int> c1, c2;
+        assert(testComparisons6(c1, c2, true, false));
+    }
+    {
+        const std::vector<int> c1(1, 1), c2(1, 2);
+        assert(testComparisons6(c1, c2, false, true));
+    }
+    {
+        const std::vector<int> c1, c2(1, 2);
+        assert(testComparisons6(c1, c2, false, true));
+    }
+    {
+        int items1[3] = {1, 2, 1};
+        int items2[3] = {1, 2, 2};
+        const std::vector<int> c1(items1, items1 + 3);
+        const std::vector<int> c2(items2, items2 + 3);
+        assert(testComparisons6(c1, c2, false, true));
+    }
+    {
+        int items1[3] = {3, 2, 3};
+        int items2[3] = {3, 1, 3};
+        const std::vector<int> c1(items1, items1 + 3);
+        const std::vector<int> c2(items2, items2 + 3);
+
+        assert(testComparisons6(c1, c2, false, false));
+    }
+    {
+        int items1[2] = {1, 2};
+        int items2[3] = {1, 2, 0};
+        const std::vector<int> c1(items1, items1 + 2);
+        const std::vector<int> c2(items2, items2 + 3);
+        assert(testComparisons6(c1, c2, false, true));
+    }
+    {
+        int items1[3] = {1, 2, 0};
+        const std::vector<int> c1(items1, items1 + 3);
+        const std::vector<int> c2(1, 3);
+        assert(testComparisons6(c1, c2, false, true));
+    }
+    {
+        const std::vector<LessAndEqComp> c1, c2;
+        assert(testComparisons6(c1, c2, true, false));
+    }
+    {
+        const std::vector<LessAndEqComp> c1(1, LessAndEqComp(1));
+        const std::vector<LessAndEqComp> c2(1, LessAndEqComp(1));
+        assert(testComparisons6(c1, c2, true, false));
+    }
+    {
+        const std::vector<LessAndEqComp> c1(1, LessAndEqComp(1));
+        const std::vector<LessAndEqComp> c2(1, LessAndEqComp(2));
+        assert(testComparisons6(c1, c2, false, true));
+    }
+    {
+        const std::vector<LessAndEqComp> c1;
+        const std::vector<LessAndEqComp> c2(1, LessAndEqComp(2));
+        assert(testComparisons6(c1, c2, false, true));
+    }
+    {
+        LessAndEqComp items1[3] = {LessAndEqComp(1), LessAndEqComp(2), LessAndEqComp(2)};
+        LessAndEqComp items2[3] = {LessAndEqComp(1), LessAndEqComp(2), LessAndEqComp(1)};
+        const std::vector<LessAndEqComp> c1(items1, items1 + 3);
+        const std::vector<LessAndEqComp> c2(items2, items2 + 3);
+        assert(testComparisons6(c1, c2, false, false));
+    }
+    {
+        LessAndEqComp items1[3] = {LessAndEqComp(3), LessAndEqComp(3), LessAndEqComp(3)};
+        LessAndEqComp items2[3] = {LessAndEqComp(3), LessAndEqComp(2), LessAndEqComp(3)};
+        const std::vector<LessAndEqComp> c1(items1, items1 + 3);
+        const std::vector<LessAndEqComp> c2(items2, items2 + 3);
+        assert(testComparisons6(c1, c2, false, false));
+    }
+    {
+        LessAndEqComp items1[2] = {LessAndEqComp(1), LessAndEqComp(2)};
+        LessAndEqComp items2[3] = {LessAndEqComp(1), LessAndEqComp(2), LessAndEqComp(0)};
+        const std::vector<LessAndEqComp> c1(items1, items1 + 2);
+        const std::vector<LessAndEqComp> c2(items2, items2 + 3);
+        assert(testComparisons6(c1, c2, false, true));
+    }
+    {
+        LessAndEqComp items1[3] = {LessAndEqComp(1), LessAndEqComp(2), LessAndEqComp(0)};
+        const std::vector<LessAndEqComp> c1(items1, items1 + 3);
+        const std::vector<LessAndEqComp> c2(1, LessAndEqComp(3));
+        assert(testComparisons6(c1, c2, false, true));
+    }
+    {
+        assert((std::vector<int>() == std::vector<int>()));
+        assert(!(std::vector<int>() != std::vector<int>()));
+        assert(!(std::vector<int>() < std::vector<int>()));
+        assert((std::vector<int>() <= std::vector<int>()));
+        assert(!(std::vector<int>() > std::vector<int>()));
+        assert((std::vector<int>() >= std::vector<int>()));
+    }
+
+    return 0;
+}

libcxx/test/support/test_comparisons.h

 //      AssertComparisonsXReturnBool        static_asserts that the operations return bool.
 //      AssertComparisonsXConvertibleToBool static_asserts that the operations return something convertible to bool.
 
 
 #ifndef TEST_COMPARISONS_H
 #define TEST_COMPARISONS_H
 
 #include <type_traits>
+#include <cassert>
 #include "test_macros.h"
 
 //  Test all six comparison operations for sanity
 template <class T, class U = T>
 TEST_CONSTEXPR_CXX14 bool testComparisons6(const T& t1, const U& t2, bool isEqual, bool isLess)
 {
+    assert(!(isEqual && isLess) && "isEqual and isLess cannot be both true");
     if (isEqual)
         {
         if (!(t1 == t2)) return false;
         if (!(t2 == t1)) return false;
         if ( (t1 != t2)) return false;
         if ( (t2 != t1)) return false;
         if ( (t1  < t2)) return false;
         if ( (t2  < t1)) return false;

 
 template <class T, class U = T>
 void AssertComparisons2ConvertibleToBool()
 {
     static_assert((std::is_convertible<decltype(std::declval<const T&>() == std::declval<const U&>()), bool>::value), "");
     static_assert((std::is_convertible<decltype(std::declval<const T&>() != std::declval<const U&>()), bool>::value), "");
 }
 
+struct LessAndEqComp {
+  int value;
+
+  LessAndEqComp(int v) : value(v) {}
+
+  friend bool operator<(const LessAndEqComp& lhs, const LessAndEqComp& rhs) {
+    return lhs.value < rhs.value;
+  }
+
+  friend bool operator==(const LessAndEqComp& lhs, const LessAndEqComp& rhs) {
+    return lhs.value == rhs.value;
+  }
+};
 #endif // TEST_COMPARISONS_H